?LeetCode刷題實(shí)戰(zhàn)279：完全平方數(shù)

示例 1：

輸入：n = 12
輸出：3 
解釋：12 = 4 + 4 + 4

示例 2：

輸入：n = 13
輸出：2
解釋：13 = 4 + 9

class Solution {
    public int numSquares(int n) {
        // 動態(tài)規(guī)劃
        int[] dp = new int[n+1];// 默認(rèn)初始化值都為0
        for(int i=1;i<=n;i++) {
          // 最壞的情況就是每次都為1相加
          dp[i] = i;
          // 對其更新
          for(int j=1;i-j*j>=0;j++) {
            dp[i] = Math.min(dp[i],dp[i-j*j]+1);//動態(tài)轉(zhuǎn)移方程
          }
        }
        return dp[n];
    }
}