题解 | #完全平方数的草料# 记忆化搜索

知识点

记忆化搜索

思路

定义状态 f[i]为总和为i的最优分解, 由于可以全分解为1, 所以任何数都是存在合法分解的

我们可以根据当前选取什么数t , 将该问题转化为一个子问题

递归终点为x为0时 返回空数组

状态数为n, 每一次转移需要枚举次, 总的时间复杂度为

AC Code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型vector
     */
    const int INF = 0x3f3f3f3f;
    vector<int> numSquares(int n) {
        vector<vector<int>> f(n + 1);

        function<void(int)> dfs = [&](int x) {
            if (x == 0 or !f[x].empty()) return;
            int mn = INF, t = 0;
            for (int i = (int)sqrt(x); i; i --) {
                dfs(x - i * i);
                if (mn > f[x - i * i].size()) {
                    mn = f[x - i * i].size();
                    t = i;
                }
            }
            f[x] = f[x - t * t];
            f[x].push_back(t * t);
        };
        dfs(n);
        sort(f[n].begin(), f[n].end());
        return f[n];
    }
};