leetcode279：完全平方数

题目链接

leetcode

题目描述

给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方。换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

/*
    状态表示：
        f[i] 表示和为 i 的完全平方数的最少数量。
    状态计算：
        对于每个 i，枚举 j
        f[i] = min(f[i], f[i-j*j] + 1)，其中 1 <= j <= i
    初始化：
        f[0] = 0
    答案：f[n]

    时间复杂度：O(n*sqrt(n))
        近似上界，得到 S = O(n*sqrt(n))
    空间复杂度：O(n)
        额外的空间 O(n) 存储状态。
*/
class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n+1, n);
        // 初始化
        f[0] = 0;

        // 状态计算
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j*j <= i; j++) {
                f[i] = min(f[i], f[i-j*j] + 1);
            }
        }

        return f[n];
    }
};

int main() {
    Solution solution;
    vector<int> n_cases = { 12, 13 };

    for (int& num : n_cases) {
        cout << "Input: n = " << num << endl;
        int result = solution.numSquares(num);
        cout << "Output: " << result << endl;
    }

    return 0;
}