Paste_Image.png
My code:
public class Solution {
public int numSquares(int n) {
if (n <= 0)
return 0;
int[] dp = new int[n + 1];
for (int i = 0; i < n + 1; i++)
dp[i] = Integer.MAX_VALUE;
dp[0] = 0;
for (int i = 0; i < n + 1; i++) {
for (int j = 1; i + j * j < n + 1; j++) {
dp[i + j * j] = Math.min(dp[i + j * j], dp[i] + 1);
}
}
return dp[n];
}
}
My test result:
Paste_Image.png
这道DP我依然没有做出来。只不过放松心态了。DP做不出来很正常。。。
仔细想想。这道题目。
网上说，最快的做法是用数论中的知识，四平方定理。也就是说，一个数，最多只需要用4个平方数就可以来表示。然后进行相应的化简等等，就可以求出来。
但我觉得数论的方法太过取巧，万一不知道这个定理呢？
于是我直接看了DP的做法。
dp[i] 表示用平方数表达i，所需要的最少个数。
那么，一个n，他有几种到达方法？
有好多种，但是论种类，就只有一种。
即， i + j * j.
所以每一轮扫描，都去最小值，直到最后，那么dp[n] 处，存的一定是，获得n的平方数的最小个数。
这个，具体就自己感觉下吧。
**
总结： DP
**
Anyway, Good luck, Richardo!
