leetcode 279. 完全平方数

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];                   }
};