（一）問題描述

279. 完全平方數 - 力扣（LeetCode）279. 完全平方數 - 給你一個整數 n ，返回 和為 n 的完全平方數的最少數量 。完全平方數 是一個整數，其值等于另一個整數的平方；換句話說，其值等于一個整數自乘的積。例如，1、4、9 和 16 都是完全平方數，而 3 和 11 不是。?示例?1：輸入：n = 12輸出：3 解釋：12 = 4 + 4 + 4示例 2：輸入：n = 13輸出：2解釋：13 = 4 + 9?提示： * 1 <= n <= 104https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked

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

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

示例?1：

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

示例 2：

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

提示：

• 1 <= n <= 10^4

（二）解決思路

????????這個問題屬于完全背包問題：想象有一個背包，它的容量是j；有一堆物品，對于物品i，它的重量是weights[i]，價值是value[i]，那么當背包填滿時，求它的價值最大是多少。 這道題的特殊指出在于它求的是最小值，思路其實是一樣的，把取最大值改成取最小值就好了。

????????在這道題里可能出現的問題：是不是所有背包都可以被“填滿“，即是否會出現某個數不能轉換成一系列完全平方數的和。答案是否定的，因為1也是完全平方數，無論如何都能用1湊滿。

????????創建dp數組，dp數組的下標j代表此時背包的容量為 j，dp[j]代表背包容量剩余j時所能存放的最大價值。在這道題中是當n中還剩下 j 這么大時，最少要用dp[j]個完全平方數填充剩下的部分j。將dp數組中每個元素的初始值設置為Integer.MAX_VALUE，即整數中的最大值，這樣它不會在取最小值時被覆蓋。不難想到 j 的最大值是n，且dp[0]=0；

????????遍歷每一個物品，物品需要滿足條件i*i<=n（否則由 i 形成的完全平方數就沒有辦法做n的組成部分啦，并且要注意這里是<=不是<）。對于每個物品，當背包剩余容量為 j 時，思考要不要放它。如果不放，完全平方數個數將是d[j]，即保持不變；如果放，那么完全平方數的個數就是上一次放東西時的剩余大小，即dp[j-i*i]，再加上這一次添加的一個物品，總物品個數就是dp[j-i*i]+1。比較放和不放的結果，去效果更好，即總個數最少的一個：Math.min(d[j],dp[j-i*i])。

class Solution {public int numSquares(int n) {//完全背包問題//完全平方數就是物品，n是背包int[] dp = new int[n+1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0]=0;for(int i=1;i*i<=n;i++){for(int j=i*i;j<=n;j++){dp[j]=Math.min(dp[j],dp[j-i*i]+1);}}return dp[n];}
}