class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
recd = [n] * (n+1)
# There are mostly n squares to sum up to `n`.
recd[0] = 0
# formular: dp[m] = min{ dp[m - i*i] + 1 }, m - i*i >=0 && i >= 1
for m in range(n+1):
i = 1
while i*i <= m:
recd[m] = min(recd[m-i*i]+1, recd[m])
i += 1
return recd[n]
https://leetcode.com/problems/perfect-squares/#/submissions/1
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...
) which sum to n.
For example, given n = 12
, return 3
because 12 = 4 + 4 + 4
; given n = 13
, return 2
because 13 = 4 + 9
.