跳台阶（动态规划/斐波那契变形）

第一行输入一个整数t，代表有t组样例:（ T<=30）
接下来的t行，都用一个整数n，表示楼梯有n级台阶（ 1<=n<=30）

输出跳到第n级台阶有多少种跳法

该题可以用动态规划来做

定义子问题：跳到第i级台阶一共有多少种跳法

状态：由子问题可以定义dp[i]为跳到第i级台阶一共有多少种跳法；

状态转移方程：由子问题可得状态转移方程dp[i]=dp[0]+dp[1]+dp[2]+....+dp[i-1];

代码如下：

#include<stdio.h>
/*
1
1
输出1
*/ 
int main()
{int t;scanf("%d",&t);int dp[35] = {0};dp[0] = 1,dp[1] = 1;   //初始化前两个状态，以后的状态都可以由前两个状态转移过来； for(int i = 2;i <= 30;i++){for(int j = 0;j < i;j++)dp[i] += dp[j];};while(t--){int n;scanf("%d",&n) ;printf("%d\n",dp[n]);}return 0;
}