完全平方数

GitHub跳转原题关系图返回列表

完全背包 DP：dp[i] 从所有不超过 i 的平方数转移，取最小值。

OJ: leetcodecn

题目 ID: perfect-squares

难度:普及

标签:动态规划完全背包

创建: 2026-07-29 12:37

更新: 2026-10-03 12:38

前置题目
luogu U663703疯狂的背包问题(5) - 完全背包问题（可行性问题）B 的 dp[i]=min(dp[i-j*j]+1) 就是在 A 教的正序完全背包转移 dp[c]=dp[c]||dp[c-v] 上把物品换成所有平方数、把可达性判定换成取最少件数，无限件这一关键设定被完整复用。luogu P1616疯狂的采药B 的 main.cpp（dp[i]=min(dp[i],dp[i-j*j]+1)）直接复用 A 教的一维完全背包状态设计与「容量正序、让本轮更新后的状态继续参与转移」这一无限次复用步骤，只是把物品集合换成平方数、把取 max 价值换成取 min 项数并把初值改为 INF，Δrank=2 属台阶题而非新范式。
后置题目
roj 3659货币系统B 判定面额冗余的那一步正是 A 教过的「物品可无限使用」设定：A 用它写 dp[i]=min(dp[i-j*j]+1) 求凑数最少件数，B 用它做可达集合的无限张闭包（main.py 里按 coin 平移取并），机制相同；B 只是在此之上叠加升序删冗余贪心与位集实现，A 更基础、B 更综合，难度差 1 级符合台阶方向。roj 2045usaco-3.1.6 邮票A 教的 min 型完全背包 dp[i]=min(dp[i-j*j]+1) 正是 B 正解「第一步：把问题换成最少张数」后照搬的转移 f(v)=1+min f(v-s)，只把物品从平方数换成邮票面值；B 的主要难度来自第一位表示可达性的位并行实现与 K·max A 上界，故属模板级复用。luogu P1853[NWERC 2004] 投资的最大效益B 的某一年解法直接复用 A 的完全背包 dp（容量维 + 可重复物品），只是从最少物品数改成最大收益并在年份上滚动

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

求和为 n 的完全平方数的最少个数。

思路

dp[i] 表示和为 i 的最少完全平方数个数。dp[i] = min(dp[i - j*j] + 1) 对所有 j*j <= i。初值 dp[0] = 0，其余 INF。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    cout << Solution().numSquares(n) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]


def main():
    print(Solution().numSquares(int(input())))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(nn)O(n \sqrt{n})。
  • 空间复杂度：O(n)O(n)。

总结

完全平方数是完全背包的变形：物品是所有平方数，每个可无限使用，求凑满目标的最少物品数。