题目
三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。
示例1:
输入:n = 3
输出:4
说明: 有四种走法
示例2:
输入:n = 5
输出:13
提示:n范围在[1, 1000000]之间
思路
- 到0阶台阶的方式:(地平线)
- 到1阶台阶的方式:1种(0->1)
- 到2阶台阶的方式:2种(0->2、到1阶台阶的方式1种(0->1->2))
- 到3阶台阶的方式:4种(0->3、到1阶台阶的方式1种、到2阶台阶的方式2种)
- 到4阶台阶的方式:7种(到1阶台阶的方式1种、到2阶台阶的方式2种、到3阶台阶的方式4种)
- 到5阶台阶的方式:13种
- ......
step1:状态表示
经验(以某一个位置为起点或结尾)+题目要求(做替换即可):
dp[i]表示:到达i位置时,一共有多少种方式。
step2:状态转移方程
以i位置的最近一次位置来划分问题——dp[i]有3种情况:
- 从i - 3位置跳3步一次性到达i位置。到i - 3位置有dp[i - 3]种方式,后面再加一步到i位置,则到i位置有dp[i - 3]种方式。
- 从i - 2位置跳2步一次性到达i位置。同理:则到i位置有dp[i - 2]种方式。
- 从i - 1位置跳1步一次性到达i位置。同理:则到i位置有dp[i - 1]种方式。
得状态转移方程为:dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。
step3:初始化
令dp[1] = 1、dp[2] = 2、dp[3] = 4,这样就不会越界。
step4:填表顺序
从左往右。
step5:返回值
返回dp[n]。文章来源:https://www.toymoban.com/news/detail-454963.html
代码文章来源地址https://www.toymoban.com/news/detail-454963.html
class Solution {
public int waysToStep(int n) {
int MOD = (int)1e9 + 7;
//处理边界条件
if(n == 1 || n == 2) {
return n;
}
if(n == 3) {
return 4;
}
//1.创建 dp 表
int[] dp = new int[n + 1]; //要访问到 n 的位置,所以 dp 表规模要是 n + 1 大小
//2.初始化
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
//3.填表
for(int i = 4; i <= n; i++) {
dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
}
//4.返回值
return dp[n];
}
}
到了这里,关于3-【斐波那契数列模型】LeetCode面试题08.01-三步问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!