最后更新
三刷
16-Jan-2017数学题= = 加一点点动态规划。
dp[n]表示 N能分成的最小数量。。
然后无非就是看一个数怎么分= =拿12来说：
9+3 1 + dp[3] ... 4+8 1 + dp[8] ... 1+11 1 + dp[11]看哪个最少就是哪个分完就保存一下，以后再利用。
Time: O(n²)
Space: O(n)public class Solution { public int numSquares(int n) { int[] dp = new int[n+1]; dp[0] = 0; for (int i = 1; i <= n; i++) { dp[i] = Integer.MAX_VALUE; for (int j = 1; j * j <= i; j++) { dp[i] = Math.min(dp[i], dp[i-j*j] + 1); } } return dp[n]; }} 一刷
给个N，计算N最少能由几个平方数组成
12 = 4 + 4 + 4 3个
13 = 4 + 9 2个用DP来做
DP[N]代表 N最少由几个平方数组成
先看 N - M² > 0 ?
代表 DP[N]的值 = DP[N - M²] + 1 其中+1的1代表 最后要+的一个平方数M² （N - M²） + M² = N DP[N-M²]在1 TO N的过程中已经计算了然后我们M+1
看看N是否可以减去一个更大的平方数如果N - (M+1)² > 0
代表 DP[N]的值 = DP[N-(M+1)] + 1但是我们不确定DP[N-(M+1)²]和DP[N-M²]谁大
所以要记录一个TEMP值 保留最小
public class Solution { public int numSquares(int n) { int[] dp = new int[n+1]; dp[0] = 0; for(int m = 1; m <= n;m++) { dp[m] = Integer.MAX_VALUE; //n - 1*1 > 0? //n - 2*2 > 0? //n - 3*3 > 0? for(int t = 1; (m - t*t)>=0;t++) { dp[m] = Math.min(dp[m],dp[m-t*t]+1); } //System.out.println(dp[m]); } return dp[n]; }} ---
二刷依然一头雾水，这个jianchao.li.fighter的题普遍数学味很大，头痛啊。。
public class Solution { public int numSquares(int n) { /* 1 1 2 1 1 3 1 1 1 4 2 2 5 4 1 6 4 1 1 7 4 1 1 1 8 4 4 9 9 10 9 1 11 9 1 1 12 4 4 4 13 9 4 */ int[] dp = new int[n+1]; dp[0] = 0; for(int i = 1; i <= n; i++) { dp[i] = Integer.MAX_VALUE; for(int t = 1; t*t <= i;t++) { dp[i] = Math.min(dp[i],dp[i-t*t]+1); } } return dp[n]; }} 其实说白了就是分解一个int为所有平方的和，怎么分数量最少。
在一开始分解的过程中就看出来了，12我分的是9+1+1+1 总共4个
而结果是 4+4+4 总共3个暴力法就是 所有可能性都试一次，比如先从最大的平方和分：
9 1 1 1 4 4 4 4 4 1 1 1 1 4 1 1 1 1 1 1 1 1 1 这种，有很多重复计算。想办法减少重复计算。那么就是DP了。 dp[n]表示分解n的最优解。dp[i] = Math.min(dp[i],dp[i-t*t]+1);
这样刚才的暴力分解就变成了个
9+3 1 + dp[3] 4+8 1 + dp[8] 1+11 1 + dp[11]省去了很多重复计算。