2023.8.18

? ? ? ? 與零錢兌換相似，本題屬于完全背包問題：完全平方數為物品，整數n為背包。

? ? ? ? 直接上代碼：

class Solution {
public:int numSquares(int n) {vector<int> dp(n+1 , INT_MAX);dp[0] = 0;for(int i=1; i*i<=n; i++){for(int j=i*i; j<=n; j++){dp[j] = min(dp[j] , dp[j-i*i]+1);}}    return dp[n];                   }
};