超级楼梯
题目描述：
有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？
Input ：
输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。
Output：
对于每个测试实例，请输出不同走法的数量
Sample Input:
Sample Output:
思路分析：
这是最容易理解的DP入门，这道题只要找出状态就行了，那么这里举个例子
方便大家理解，如果是给出是第4级台阶:
第一种： 3 -> 4
第二种： 2 -> 4
以此类推将4换成3或2继续递推，那么就有了一个公式：
F（n）=F（n-1）+F（n—2）.
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
void LemonDP(int c)
{
int dp[c+1];
dp[1]=0;
dp[2]=1;
dp[3]=2;
for(int i=4;i<=c;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
cout << dp[c] << endl;
}
int main()
{
int b,c;
cin >> b;
while(b--)
{
scanf("%d",&c);
LemonDP(c);
}
}
转载：https://blog.csdn.net/xiaosuC/article/details/104521673
查看评论