力扣-279题 完全平方数（C++）- 完全背包

题目链接：https://leetcode.cn/problems/perfect-squares/
题目如下：

class Solution {
public:
    int numSquares(int n) {
        //由题意可得，背包容量为n，物品为完全平方数，且物品数量不限
        //可得，这是一个完全背包问题
        //所以，dp[i]为组成i的最少完全平方数
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;

        //完全背包+求组合：外物品，内容量不倒序    0-1背包+求组和：外物品+内容量倒序
        for(int i=1;i*i<=n;i++){
            for(int j=1;j<=n;j++){
                if(j-i*i>=0) dp[j]=min(dp[j-i*i]+1,dp[j]);
            }
        }

        return dp[n];

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20