跳台阶

链接:https://www.nowcoder.com/acm/contest/90/A
来源:牛客网

题目描述

小明在坐景驰科技研发的无人车到达了目的地。
景驰科技(JingChi.ai)是一家由人工智能技术驱动、以无人驾驶技术为核心的智能出行公司。它将打造面向中国市场的全无人驾驶。
从无人车下来以后,小明看到了一个长长的楼梯。
有一个n级台阶的楼梯,小明一次可以向上跳1步,两步,甚至是n步,请问小明跳到n级台阶有多少种跳法?

输入描述:

第一行输入一个整数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;
}