面试题 08.01. 三步问题
https://leetcode.cn/problems/three-steps-problem-lcci/
难度简单80
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:
输入：n = 3 输出：4 说明: 有四种走法
示例2:
输入：n = 5 输出：13
提示:
- n范围在[1, 1000000]之间
通过次数52,929提交次数144,463
class Solution {
public int waysToStep(int n) {
//简单dp
//边界：f(1)=1,f(2)=2,f(3)=4
//动态转移方程：f(n)=f(n-1)+f(n-2)+f(n-3)
int x=1,y=2,z=4;
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
int ans =0;
for(int i=4;i<=n;i++)
{
ans = ((x+y)%1000000007+z)%1000000007;
x = y;
y = z;
z = ans;
}
return ans;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/69049.html
