Given a positive integern, find the least number of perfect square numbers (for example,1, 4, 9, 16, ...) which sum ton.
For example, givenn=12, return3because12 = 4 + 4 + 4; givenn=13, return2because13 = 4 + 9.
【题目分析】
一个数可以由一些完全平方数相加得到，例如1,4,9,16,...
给定一个数n，求出使得相加结果为n所需最少的完全平方数的个数。
【思路】
1. 递归
对于一个数，我们怎么求它的由哪些完全平方数相加得到的呢？
首先找到距离这个数最近的完全平方数m = x*x，我们从1~x中选择一个数，求出n中包含z个x*x，我们在递归求出n-z*x*x所包含的完全平方数。遍历1~x，返回其中最小的结果。
2. 动态规划
动态规划用 dp[i] 数组存储第 i 个数的完美平方数。递推式为：dp[i] = Math.min(dp[j] + dp[i-j], dp[i])，认为 i 的完全平方数是从和为 i 的两个完全平方数 dp[j] 和 dp[i-j]之和，然后从中取最小。
3. 改进后的动态规划
任何数字都可以表示成为一个普通数字加上一个完全平方数，因此有如下表格：
任何数的表示形式
如图所示，红色部分表示平方数，所有的数都可以看做一个普通数加上一个完美平方数，那么递推式就变为了：dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j])。
java递归实现：
public class Solution {
public int numSquares(int n) {
int count = n;
int nearest = (int)Math.sqrt(n);
if(n == 0) return 0;
if(nearest*nearest == n) return 1;
for(int i = nearest; i >= 1; i--) {
int cur = 0, num = n, t = i*i;
while(num - t >= 0) {
num -= t;
cur++;
}
if(cur < count){
count = Math.min(numSquares(num)+cur, count);
}
}
return count;
}
}
java 动态规划实现：
public class Solution {
/*
动态规划的思想来解决，递推公式dp[i] = Math.min(dp[j] + dp[i-j], dp[i])
*/
public int numSquares(int n) {
int[] array = new int[n+1];
Arrays.fill(array, Integer.MAX_VALUE);
array[1] = 1;
for(int i = 2; i <=n; i++) {
int sqr = (int)Math.sqrt(i);
if(sqr*sqr == i) array[i] = 1;
else{
for(int j = 1; j <= i/2; j++) {
array[i] = Math.min(array[j]+array[i-j], array[i]);
}
}
}
return array[n];
}
}、
改进的动态规划实现：
public class Solution {
/*
改进后动态规划，递推公式dp[i+j*j] = Math.min(dp[i]+1, dp[i+j*j])
*/
public int numSquares(int n) {
int[] array = new int[n+1];
Arrays.fill(array, Integer.MAX_VALUE);
for(int i = 1; i*i <= n; i++) {
array[i*i] = 1;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; i+j*j <= n; j++) {
array[i+j*j] = Math.min(array[i]+1, array[i+j*j]);
}
}
return array[n];
}
}
