perfect_squares.py 文件源码

def numSquares2(n):
    dp = [sys.maxint for i in range(n + 1)]
    dp[0] = 0
    for i in range(0, n + 1):
        for j in range(1, int(math.sqrt(n - i)) + 1):
            if i + j * j <= n:
                dp[i + j * j] = min(dp[i + j * j], dp[i] + 1)
    return dp[n]


# print(numSquares2(4))

# ??, ????????, ???????????????
# ??: ????????:
# 1. ?????????????????????4????????????????4?????????????????????1,2,3?4?????
# 2. ???????????4????????4?????????????2?8,3?12??
# 3. ???????8?7?????????4????????
# 4. ???????????????????????????1?2?????????????0