題目來(lái)自nyist第76題，如下：

描述

對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出不同走法的數(shù)量。

這題可以用許多解法，DP遞推式：dp[i] = dp[i-1]+dp[i-2]，其中dp數(shù)組為到達(dá)第i級(jí)階梯的走法i可以由i-1級(jí)跨一步或者i-2級(jí)跨兩步走來(lái)，所以達(dá)到第i級(jí)的走法等于兩者相加，由于本題有限定1到1級(jí)為0，并且，遞推式中需要已知i-2的dp值，所以可以先列出（手動(dòng)賦值）1、2、3的dp值，然后用for循環(huán)求出dp值。本題采用打表后直接輸出的方法，可以減少?gòu)?fù)雜度，避免每次輸入一個(gè)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; } 有了遞推式，本題還可以用遞歸求解。有輸出可知本題就是斐波拉契數(shù)列。