完全平方数的和

_sum.py

#!/usr/bin/python3
# -*-coding:utf-8-*-

__author__ = "Bannings"

def _sum(n: int) -> int:
    dp = [[[]]] + [[] for _ in range(n)]
    max_num = int(n**0.5)
    for i in range(1, max_num + 1):
        num = i * i
        for index in range(num, n + 1):
            position = index - num
            dp[index] += [collection + [num] for collection in dp[position]]

    # return max(dp[-1])
    return len(max(dp[-1]))

def _sum2(n: int) -> int:
    def _recursive(num: int) -> []:
        if num == 0: return []
        if num == 1: return [1]
        root = int(num**0.5)
        return [root * root] + _recursive(num - root * root)
    # return _recursive(n)
    return len(_recursive(n))

def _sum5(n: int) -> int:
    stack, max_root, ans = set([n]), int(n**0.5), 0
    while stack:
        ans, next_stack = ans + 1, set()
        for num in stack:
            for root in range(1, max_root + 1):
                square = root * root
                if num == square: return ans
                elif square > num: break
                else: next_stack.add(num - square)

        stack = next_stack
    return ans

if __name__ == '__main__':
    print(_sum5(5))
    print(_sum5(12))
    print(_sum5(15))
    print(_sum5(2595321))