问题描述 链接到标题

279.完全平方数

解题思路 链接到标题

本题可以转化成一个完全背包问题，“物品”即{1, 4, 9, 16,...}等完全平方数，体积限制即所给的整数$n$。

代码 链接到标题 

class Solution {
  private:
    int min(int a, int b) {
        return a < b ? a : b;
    }

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