面试题 08.01. 三步问题

题干

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

示例1:

输入：n = 3 

输出：4

说明: 有四种走法

示例2:

输入：n = 5

输出：13

提示:

n范围在[1, 1000000]之间

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/three-steps-problem-lcci

 

解答

解法一：递归

递归调用step函数，将台阶记为n，每次减去123步，能够达到0则用ans记录次数+1

结果虽然能过样例，但是超时了

class Solution {
    int ans=0;
    public int step(int n){
            if(n>0){
                for(int i=1;i<=3;i++){
                    step(n-i);
                }
            }
            else if(n==0){
                ans++;
            }
            else if(n<0){
                return 0;
            }
            return 0;
        }

    public int waysToStep(int n) {
        
        if(n>0){
            step(n);
        }
        return ans;
    }
}

方法二：动态规划

①定义

动态规划dp[i]表示走到第i阶台阶时有多少种方法了

②状态转移方程

dp[i]=dp[i-1]+1步

dp[i]=dp[i-2]+2步

dp[i]=dp[i-3]+3步

③初始化

dp[0]=0

dp[1]=1

dp[2]=2

dp[3]=4

④溢出状态

结果可能很大，你需要对结果模1000000007

取模，对两个较大的数之和取模再对整体取模，防止越界（这里也是有讲究的）

假如对三个dp[i-n]都 % 1000000007，那么也是会出现越界情况（导致溢出变为负数的问题）

因为如果本来三个dp[i-n]都接近 1000000007 那么取模后仍然不变，但三个相加则溢出

但对两个较大的dp[i-n]:dp[i-2],dp[i-3]之和mod 1000000007，那么这两个较大的数相加大于 1000000007但又不溢出。取模后变成一个很小的数，与dp[i-1]相加也不溢出

class Solution {
    public int waysToStep(int n) {
        if(n==1){
            return 1;
        }
        else if(n==2){
            return 2;
        }
        else if(n==3){
            return 4;
        }
        else{
            int[] dp=new int[n+1];
            dp[0]=0;
            dp[1]=1;
            dp[2]=2;
            dp[3]=4;
            for(int i=4;i<=n;i++){
                dp[i]=(dp[i-1]+(dp[i-2]+dp[i-3])%1000000007)%1000000007;
            }
            return dp[n];
        }  
    }
}