完全平方数

题意

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

思路

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

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19#!/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(n \sqrt{n})$ 。
空间复杂度： $O(n)$ 。

总结

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

目录

题意

思路

代码

复杂度

总结