完美平方數(shù)都可以看做一個普通數(shù)加上一個完美平方數(shù)
如圖所示要出，紅色部分表示平方數(shù)衩辟，所有的完美平方數(shù)都可以看做一個普通數(shù)加上一個完美平方數(shù)，那么遞推式就變?yōu)榱耍篸p[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j])。
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
for(int i = 1; i<=n ;i++){
dp[i] = i; // 最多都由1組成
for(int j = 1; j*j<=i; j++){
dp[i] = Math.min(dp[i], dp[i-j*j]+1);
}
}
return dp[n];
}
}
