前言:
这篇文章还是是为了帮助一些
像我这样的菜鸟
找到简单的题解
上了很久的csp复习课
我发现我动态规划的题解少之又少
这几期我来更新一下动规的题
问题描述:
一个楼梯有n级台阶，小苏同学从下往上走，一步可以跨1级，也可以跨2级，也可以跨3级。
问：他走到第n级楼梯有多少种走法？
输入格式
一行一个整数 n（0<n≤100000）。
输出格式
一行一个数，为小苏同学走到第n级台阶的方案数。
结果可能很大，请输出对1000000007（1e9+7）取模后的结果。
样例输入
100
样例输出
347873931
问题解析:
和上一期一样
动态规划 台阶问题一(爱思创)_吾乃狙击神蛐的博客-CSDN博客
只不过要加上他的前三个台阶
转换方程为:
f[i]=f[i-1]+f[i-2]+f[i-3];完整代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;//数组大小
const int mod=1e9+7;//按题目要求
int f[N];//也可以叫dp我们老师写f
int main()
{
int n,i;
cin>>n;
f[0]=1;//设置地面
f[1]=1;//设置第一阶
f[2]=2;//设置第二阶
for(int i=3;i<=n;i++)
{
f[i]=((f[i-1]+f[i-2])%mod+f[i-3])%mod;//方程但要取模
}
cout<<f[n]%mod;//输出结果
return 0;
}