完美平方数从递归到迭代

algorithm

完美平方数

• 完美平方数，题目大意，给定一个数$n$，$n$可以表示为一个或者多个数的平方和，问给定一个数，求最少需要多少个数的平方和能够等于给定的数$n$？
• 理解这个题目之后，可以发现所有的数据都至少可以表示为1的和。例如：$2=1^2+1^2$，$13 = 3^2+2^2$。从最简单的case分析，一个数$n=1^2+(n-1)$，所以，假设$f(n)$表示n最少需要的数的个数，那么求得$f(n)$，根据最简单情况，可以$f(n)= 1 + f(n-1)$，同时$f(n) = f(n-2^2) + 1$ ....
• 所以我们可以枚举比$\sqrt{n}$小的数，然后获取最小的个数

方法一：递归

• 直观想法，求解的是$f(n)$，依据上面的分析，$f(n)$可以表示为多个形式，例如：$f(n) = f(n-1) +1 = f(n-2^2)+1=f(n-3^2)+1 ....$，所以$f(n)$可以转化为更小的子问题来解决。
• 最基本情况是：$n=1$ 则返回$f(1)=1$
• 最后的情况,$f(n) = f(n-(\sqrt{n})^2) + 1$。
• 所以枚举的最大值为$\sqrt{n}$

    int numSquares(int n) { return dfs(n); }
    int dfs(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int x = sqrt(n);// 最大的枚举值，最小的从1开始
        int c = INT_MAX;
        for (int i = 1; i <= x; i++) {
            auto y = dfs(n - i * i);
            c = min(c, y + 1);
        }
        return c;
    }

• 时间复杂度:$T(n) =\sum_{i=1}^{\sqrt{n}}{T(n - i)} = O(x^n),x \in (1,2)$。
• 空间复杂度:函数调用

方法二：转化为备忘录递归

• 上述方式存在子问题重复计算的情况，例如计算$f(n)$,需要计算 $f(n-1),f(n-4),f(n-9) \cdots$，最后会转化为基本case。例如$f(4),f(9)$等等,可以发现非常多的子问题需要重新计算，我们用map，也可以用数组，来缓存已经计算完的数据。对于已经获取的数据直接返回结果。
• 对于已经计算出来的符号排列结果用map来保存，例如map[3]=3，下次计算$f(3)$的时候可以直接使用

    int numSquares(int n) { return dfs(n); }
    int dfs(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (cache.find(n) != cache.end()) {// 已计算
            return cache[n];
        }
        int x = sqrt(n);
        int c = INT_MAX;
        for (int i = 1; i <= x; i++) {
            auto y = dfs(n - i * i);
            c = min(c, y + 1);
        }
        cache[n] = c;//缓存结果
        return c;
    }

• 时间复杂度：$T(n) = O(n^{\frac{3}{2}})$，0到$n$的数都需要计算，并且每个数需要计算$\sqrt{n}$次。
• 空间复杂度：递归使用的栈空间$O(\sqrt{n})$

方法三：完美平方数（转化为迭代计算）

• 从第二步，能看出，我们可以从基本情况（小规模的问题），来推导更为大的规模。
• 假设$f(n)$ 表示和为$n)$的最小个数。
• 如果我们知道$f(1)$，那么$f(2) = f(1)+1,f(3) = f(2) +1 ,f(4)= f(2^2)+0$，一直递推到$f(n)$。

• 基础情况：$f(0) =0,f(1)=1$

     int numSquares(int n) { return dyp(n); }
    int dyp(int n) {
        if (n <= 0)
            return 0;
        if (n == 1) {
            return 1;
        }
        vector<int> dp(n + 1, INT_MAX);
        dp[1] = 1;
        dp[0] = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = sqrt(i); j >= 1; j--) {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

• 时间复杂度:$O(n^{\frac{3}{2}})$
• 空间复杂度：$O(n)$

其他

• 还有其他的方法，例如数学方法，可以参考leetcode讨论区