最后更新
三刷
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]
省去了很多重复计算。