LeetCode-面试题08.01 三步问题 C/C++实现 超详细思路及过程[E]
🎈归属专栏：深夜咖啡配算法
🚗个人主页：Jammingpro
🐟记录一句：摆了一个周末了，不能摆了，努力起来！！
文章目录
- LeetCode-面试题08.01 三步问题
- 🚗题目
- 🚆题目描述
- 🚆题目示例
- 🚆提示
- 🚗题解
- 🚆动态规划法
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} Tn= T n − 3 T_{n-3} Tn−3+ T n − 2 T_{n-2} Tn−2+ T n − 3 T_{n-3} Tn−3。从题意可知， T 0 T_{0} T0=1， T 1 T_{1} T1=1， T 2 T_{2} T2=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