LeetCode——面试题 08.01. 三步问题_有一个小孩正在上楼梯,楼梯有n阶台阶,小孩儿一次可以上1阶,2阶,3阶。实现一种方法

题目描述：

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

示例1:
 输入：n = 3 
 输出：4
 说明: 有四种走法
 
示例2:
 输入：n = 5
 输出：13
 
提示:
n范围在[1, 1000000]之间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

解决思路：

动态规划

参考文章：动态规划之青蛙跳台阶
动态规划基本思想

动态规划的实质是分治思想和解决冗余。因此，动态规划是一种将问题实例分解为更小的/相似的子问题，并存储子问题的解，使得每个子问题只求解一次，最终获得原问题的答案，以解决最优化问题的算法策略。

与贪心法的关系：
1.与贪心法类似，都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。
2.贪心法选择当前最优解，而动态规划通过求解局部子问题的最优解来达到全局最优解。

与递归法的关系：
1.与递归法类似，都是将问题实例归纳为更小的、相似的子问题。
2.递归法需要对子问题进行重复计算，需要耗费更多的时间与空间，而动态规划对每个子问题只求解一次。对递归法进行优化，可以使用记忆化搜索的方式。它与递归法一样，都是自顶向下的解决问题，动态规划是自底向上的解决问题。

递归问题——>重叠子问题——> 1.记忆化搜索（自顶向下的解决问题）；2.动态规划（自底向上的解决问题）

Java代码：

递归，自顶向下，但是该方法会超时

class Solution {
    public int waysToStep(int n) {
        int mod = 1000000007;
        if(n<=2) return n;
        if(n==3) return 4;
        //递归
        return ((waysToStep(n-1)+waysToStep(n-2))%mod+waysToStep(n-3))%mod;
    }
}
1
2
3
4
5
6
7
8
9

回溯，自底向上

class Solution {
    public int waysToStep(int n) {
        int mod = 1000000007;
        //定义初始数组
        int[] d = new int[]{1,2,4};
        //定义中间变量
        int temp1 = 0;
        int temp2 = 0;
        //回溯（动态规划）
        if(n<=2) return n;
        if(n==3) return 4;
        if(n>3) {
            for (int i = 4; i <= n ; i++) {

                //i++之后，现在的d[1]变成d[0],现在的d[2]变成d[1],新产生的d[2]是d[2]
                temp1 = d[1];
                temp2 = d[2];

                //d[2]=d[0]+d[1]+d[2];//不要忘记取余，否则数据会溢出
                d[2]=( (d[0]+d[1])%mod+d[2] )%mod;
                //更新d[0]和d[1]
                d[0] = temp1;
                d[1] = temp2;
            }
        }
        return d[2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28