【手撕算法|动态规划系列No.2】leetcode面试题 08.01. 三步问题

点击直接跳转到该题目

🥙题目描述

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

示例2：

提示:

🎂算法原理+题目解析

步骤1（最重要）状态表示

步骤2（最难）：状态转移方程

步骤3：初始化

步骤4：填表顺序

步骤5：返回值

本题尤其要注意提示部分，由于返回的数据值比较大，所以我们需要进行模运算，尤其是返回值的处理，请看：dp[i]=((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;这里进行模运算的时候并不是统一加完之后一起进行模运算，而每加一次dp值就需要进行模运算，即加一次dp值就需要进行一次模运算、加一次dp值就需要进行一次模运算。

🍰解题代码

class Solution {
public:
    int waysToStep(int n) {
        const int MOD =1e9+7; 
        //创建dp表
        vector<int> dp(n+1);
        
        //初始化处理边界条件
        if(n==1||n==2) return n;
        if(n==3) return 4;
        
        dp[1]=1;dp[2]=2;dp[3]=4;

        //填表
        for(int i=4; i<=n; i++)
            dp[i]=((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;

        //返回值
        return dp[n];
    }
};

🍱总结

该问题依然是属于动态规划类型的题目，思考的时候大体就是按照那5步（状态表示、状态转移方程、初始化来进行边界处理、填表顺序、返回值）来想，在进行代码编写的时候基本就是按照那4步进行编写（创建dp表，初始化、填表、返回值）。