Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
给出一个正整数n，找到相加得到n的最少个数的完全平方数字（比如1， 4， 9， 16）
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
动态规划解。这种类型的题目已经接触很多了，比较加上每个完全平方数字得到的个数，取最小的那个就可以了。定义dp[i]：相加得到i的最少个数的完全平方数字，递推式：dp[i] = min(dp[i], dp[i - square_number]) (square_number < i)
class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ dp = [0] + [n + 1] * n for i in range(1, n + 1): index = 1 square_number = 1 while square_number <= i: dp[i] = min(dp[i - square_number] + 1, dp[i]) index += 1 square_number = pow(index, 2) return dp[n]新闻热点
疑难解答
