【DP入门】超级台阶

题目来自nyist第76题，如下：

描述

对于每个测试实例，请输出不同走法的数量。

这题可以用许多解法，DP递推式：dp[i] = dp[i-1]+dp[i-2]，其中dp数组为到达第i级阶梯的走法i可以由i-1级跨一步或者i-2级跨两步走来，所以达到第i级的走法等于两者相加，由于本题有限定1到1级为0，并且，递推式中需要已知i-2的dp值，所以可以先列出（手动赋值）1、2、3的dp值，然后用for循环求出dp值。本题采用打表后直接输出的方法，可以减少复杂度，避免每次输入一个m就重新算一次。

代码如下：

#include <stdio.h>int dp[45]; int main(){	int m,i,n;	scanf("%d",&n);	dp[2] = 1;dp[1] = 0;dp[0]= 0;dp[3] = 2; 	for(i = 4;i<=41;i++)	{		dp[i] = dp[i-1]+dp[i-2];	}	while(n--)	{		scanf("%d",&m); 		PRintf("%d/n",dp[m]); 	}	return 0; } 有了递推式，本题还可以用递归求解。有输出可知本题就是斐波拉契数列。