leetcode热题100 P279 完全平方数

---

时间轴

时间轴

2026-03-20

init

动态规划

---

题目：

P279 完全平方数

https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked

动态规划

#include <vector>
using std::vector;

class Solution {
    public:
        int numSquares(int n) // 12
        {
                int i, j;
                vector<int> perfect_squares;
                vector<int> dp(n + 1, n + 1);

                for (i = 1; i * i <= n; i++)
                        perfect_squares.push_back(i * i); // 1 4 9

                dp[0] = 0;

                for (i = 1; i <= n; i++) {
                        for (j = 0; j < perfect_squares.size() && perfect_squares[j] <= i; j++)
                                dp[i] = std::min(dp[i], dp[i - perfect_squares[j]] + 1);
                }

                return dp[n];
        }
};

#include <cstdio>
int main()
{
        Solution S;
        int num = S.numSquares(12);
        printf("%d\n", num);
        num = S.numSquares(13);
        printf("%d\n", num);
}