LeetCode 08.01 三步问题[递归/动态规划]

这是我参与更文挑战的第 4 天，活动详情查看： 更文挑战

题目描述

三步问题

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。

示例 1：

输入：n = 3 
输出：4
说明: 有四种走法
复制代码

示例 2：

输入：n = 5
输出：13
复制代码

提示

• n 范围在 [1, 1000000] 之间

思路分析

三步问题同斐波那契数列和青蛙跳台阶问题非常类似，如果那你掌握了这三道题，那你也就掌握了这类问题的通用解法，小孩有三种跳法，1，2，3。我们可以先计算 n=1，2，3 这这三种情况下上楼梯有几种方式，分别是 1，2，4。递归问题解答的常规思路是，一个大问题能否分解为多个子问题，子问题和父问题的解决思路一致，直到最小子问题，判断终止条件，返回/返回值。

同理我们的 n 可以分解为 （n-1）+ （n-2）+ （n-3）三种情况之和，我们的终止条件就是n = 1,n = 2,n = 3 这三种情况，但是如果直接这么解答的话会遇到超时，因为 n 的最大值还是很大的，这种接法的时间复杂度是${O(2^n)}$，所以耗时严重。不过也可以优化到${O(n)}$。

同时我们也可以使用动态规划解法，动态的改变数组或几个临时变量的值，大大降低时间复杂度

代码展示

解法一：时间复杂度是${O(2^n)}$，空间复杂度是${O(1)}$。

    public int waysToStep(int n) { //5
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        if (n == 3){
            return 4;
        }

        return ((waysToStep(n-1) + waysToStep(n-2)) % 1000000007 + waysToStep(n-3)) % 1000000007;
复制代码

运行后，提示运行超时

运行失败:
				Time Limit Exceeded
				测试用例:61
				stdout:
复制代码

因为这种写法是很耗时的，我们可以尝试用备忘录解法进行优化，对于计算过的值都存到数组中，避免多次的重复计算。将时间复杂度降到${O(n)}$，这时的空间复杂度为${O(n)}$。解法如下：

int[] cache;
public int waysToStep(int n) { //5
        cache = new int[n+1];
        return waysToStepInternal(n);
    }    
public int waysToStepInternal(int n) {
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        if (n == 3){
            return 4;
        }
        if (0 != cache[n]){
            return cache[n];
        }
        cache[n] = ((waysToStepInternal(n-1) + waysToStepInternal(n-2)) % 1000000007 + waysToStepInternal(n-3)) % 1000000007;
        return cache[n];
}
复制代码

该解法运行成功，但是也非常耗时，仅仅超过百分之五的用户。因为 n 的最大值也可以很大。

解答成功:
				执行耗时:111 ms,击败了5.09% 的Java用户
				内存消耗:141.5 MB,击败了5.09% 的Java用户
复制代码

而且有时候改解法也会超时，取决于测试时服务器的使用情况。

解法二：该方法的时间复杂度是${O(n)}$，空间复杂度是${O(n)}$。

我们使用动态规划，创建一个数组，不断将每次计算后的值放到数组中，直到返回最后一个值。

    public int waysToStep(int n) { //5
        int[] cache = new int[n+1];
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        if (n == 3){
            return 4;
        }
        cache[1] = 1;
        cache[2] = 2;
        cache[3] = 4;
        for (int i = 4; i <= n ; i++) { //7
           cache[i] = ((cache[i-1] + cache[i-2])% 1000000007 +cache[i-3])% 1000000007;
        }
        return cache[n];

    }
复制代码

运行成功，耗时如下：

解答成功:
				执行耗时:39 ms,击败了48.33% 的Java用户
				内存消耗:42 MB,击败了61.76% 的Java用户
复制代码

该解法的耗时差不多接近平均水平，你可能有点疑问，上一个解法和该解法的时间复杂度都是${O(n)}$，为什么上一个解法耗时这么久，原因在于上一个解法是递归调用函数，而该解法是直接调用数组中的值相加，举个例子：1000 个函数嵌套调用远比 1000 行代码耗时得多，因为要不断的出栈和入栈。

我们还可以进行进一步的优化，因为 n 的所有情况是由 n-1，n-2，n-3 这三种情况加起来的，我们可以用四个变量来表示这四个值，动态的变化这四个变量的值，将空间复杂度优化到${O(1)}$。

解法三：

    public int waysToStep(int n) { //5
        int[] cache = new int[n+1];
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        if (n == 3){
            return 4;
        }
        int a = 1;
        int b = 2;
        int c = 4;
        int d = 0;
        for (int i = 4; i <= n ; i++) { //7
            d = ((a+b)%1000000007+c)%1000000007;
            a = b;
            b = c;
            c = d;
        }
        return d;
复制代码

运行成功，耗时如下：

解答成功:
				执行耗时:25 ms,击败了77.99% 的Java用户
				内存消耗:41.9 MB,击败了62.17% 的Java用户
复制代码

总结

简单的一道题，我们从一开始的递归超时到使用备忘录解法，就算递归+备忘录解法耗时还是很严重，在 n 较大时，因为递归调用函数，多个函数嵌套涉及函数的出栈入栈非常耗时，后面我们使用动态规划解法，再进一步优化使用变量替代数组。

最后还有一个最大值越界问题，因为单个数是不会越界的，只有在两两相加时才会越界，没有必要做过多的求模处理。