这篇文章还是是为了帮助一些
像我这样的菜鸟
找到简单的题解
上了很久的csp复习课
我发现我动态规划的题解少之又少
这几期我来更新一下动规的题
有 n 阶台阶,每次小 A 可以上 1 阶或者 2 阶,
但是如果有一步上了 2 阶,小 A 会变累,使得他下次只能上 1 阶,
请问上完 n 阶台阶有多少种方法?
一个整数n(0≤n≤1e7)。
一个整数,表示方法数,结果可能很大,输出结果请对1e9+7取模。
2
2
本题是前三道的稍微进价
动态规划 台阶问题三(爱思创)_吾乃狙击神蛐的博客-CSDN博客
别看有走两级累这一点
其实只要把先走两级再走一级想为走三级即可
转换方程为:
f[i]=(f[i-1]+f[i-3])
- #include
- using namespace std;
- const int N=1e7+5;
- const int mod=1e9+7;//取模
- int f[N],a[N];
- int main()
- {
- int n,i;
- cin>>n;
- f[0]=1;
- f[1]=1;
- f[2]=f[1]+f[0];//设置初始
- for(int i=3;i<=n;i++)
- {
- f[i]=(f[i-1]+f[i-3])%mod;//转换方程
- }
-