跳转至

279 完全平方数

思路:完全背包应用,物品对应完全平方数i * i,容量对应和,weight[i]对应完全平方数i * i,value[i]对应个数1

i的范围为[1, sqrt(n)]

j的范围为[0, n]

注意初始化dp为INT_MAX,因为求的最小数量

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

由二维数组解法改编而成

dp[i - j * j]下标比dp[i]小,所以j可以从小到大遍历

这非常重要,这是和01背包问题的区别

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