題目描述

給你一個整數 n ，返回 和為 n 的完全平方數的最少數量 。

完全平方數 是一個整數，其值等于另一個整數的平方；換句話說，其值等于一個整數自乘的積。例如，1、4、9 和 16 都是完全平方數，而 3 和 11 不是。

class Solution {public int numSquares(int n) {int[] nums = new int[102];for(int i = 1; i <= 101; i++){nums[i] = i*i;}int[] dp = new int[n+1];    //dp數組是最后答案，和為n最少個數for(int i = 1; i <= n; i++){dp[i] = i;  //最差的可能是全1for(int j = 1;i-nums[j]>=0;j++){dp[i] = Math.min(dp[i],dp[i-nums[j]]+1);    //輪流用不超過n的完全平方數做替換}}return dp[n];}
}

小結：還是一維的dp，要考慮每個數用完全平方數與不用完全平方數之間哪個最優，且不大于該數的完全平方數都要試一遍。