# 279.完全平方数

## 问题描述
[279.完全平方数](https://leetcode.cn/problems/perfect-squares/)

## 解题思路
本题可以转化成一个[完全背包问题](https://zwyyy456.vercel.app/zh/posts/tech/unbounded-knapsack-problem/)，“物品”即`{1, 4, 9, 16,...}`等完全平方数，体积限制即所给的整数$n$。

## 代码
```cpp
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];
    }
};
```