🎈归属专栏：深夜咖啡配算法
🚗个人主页：Jammingpro
🐟记录一句：摆了一个周末了，不能摆了，努力起来！！

LeetCode-面试题08.01 三步问题

标签：动态规划、记忆化搜索、数学

---

🚗题目

🚆题目描述

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

🚆题目示例

示例 1:

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

示例 2:

输入：n = 5
输出：13

🚆提示

n范围在[1, 1000000]之间

---

🚗题解

🚆动态规划法

这一题与70.爬楼梯问题类似【传送门】，当我要爬到第n个台阶时，我可以是从n-1号台阶爬1个台阶后到达，可以是从n-2号台阶爬2个台阶后到达，还可以是从n-3号台阶爬3个台阶后到达。因而，可以得到递推公式$T_n$=$T_{n-3}$+$T_{n-2}$+$T_{n-3}$。从题意可知，$T_0$=1，$T_1$=1，$T_2$=2。得到初始化的几个数值及递推公式，我们就可以实现代码了👇

class Solution {
public:int waysToStep(int n) {const int MOD = 1000000007;if(n == 0 || n == 1) return 1;if(n == 2) return 2;int t0 = 1, t1 = 1, t2 = 2;for(int i = 3; i <= n; i++){int tmp = ((t0 + t1) % MOD + t2) % MOD;t0 = t1;t1 = t2;t2 = tmp;}return t2;}
};

文章结语：这道题是一道简单题，算是动态规划入门类题目了！！
🎈欢迎进入深夜咖啡配算法专栏，查看更多文章。
如果上述内容有任何问题，欢迎在下方留言区指正b(￣▽￣)d