动态转移方程：动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i表示当前数字，jj表示平方数 dp[i - j * j] + 1解释如下： 假设m满足最少完全平方个数,m = f(n) n满足 ∑(A[i] * A[i]) = n 假设k满足最小值m的时候的值，则令 d + k * k = n, d >= k 可得 f(d) + f(k * k) = f(n), f(k * k)只有k^2一个数， 又有d = n - k * k 综上可得 f(n - k * k) + 1 = f(n) 参考链接：https://leetcode-cn.com/problems/perfect-squares/solution/hua-jie-suan-fa-279-wan-quan-ping-fang-shu-by-guan/ 算法时间复杂度： O(nsqrt(n))； 空间复杂度：O(n)
class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ """ 动态转移方程解释： 假设m满足最少完全平方个数,m = f(n) n满足 ∑(A[i] * A[i]) = n 假设k满足最小值m的时候的值，则令 d + k * k = n, d >= k 可得 f(d) + f(k * k) = f(n), f(k * k)只有k^2一个数， 又有d = n - k * k 综上可得 f(n - k * k) + 1 = f(n) """ dp = [0] * (n + 1) for i in range(1, n + 1): dp[i] = i #最坏情况是每次都加1，即为，1^2的和 for j in range(1, int(i ** 0.5) + 1): dp[i] = min(dp[i], dp[i - j * j] + 1) return dp[n] x = Solution() x.numSquares(12)