2013蓝桥 第39级台阶

第三题 题目标题: 第39级台阶     小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!     站在台阶前，他突然又想着一个问题：     如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？     请你利用计算机的优势，帮助小明寻找答案。 要求提交的是一个整数。

注意：不要提交解答过程，或其它的辅助说明文字。

一开始我很激动，以为终于遇到自己会的简单dp了，就直接写了，结果就错了，因为题目要求第一步先迈左脚，最后迈右脚，这样算出来是全部的情况，显然不对

#include<stdio.h> int dp(int n) { if(n==1)return 1; if(n==2)return 2; else{ return dp(n-1)+dp(n-2); } } int main() { printf("%d\n",dp(39)); }

用二维数组，行表示走到第i阶，列j表示到这一阶迈的是左脚还是右脚

第一步先迈左脚，最后第39阶迈右脚

#include<stdio.h> int main() { int d[40][2];//行表示有40个台阶0~39，列表示 0，1分别表示 左脚，右脚 d[0][0]=d[1][1]=0; //这两种都是第一阶用右脚走的情况，不符合题意，置0 d[0][1]=d[1][0]=1;//这两种是第一阶用左脚走到情况，符合题意，置1 int i; for(i=2;i<=39;i++) { d[i][0]=d[i-1][1]+d[i-2][1]; //这一步是0左脚，那上一步走的一定是右脚1 d[i][1]=d[i-1][0]+d[i-2][0];//这一步是1右脚，上一步走的一定是左脚0 } printf("%d\n",d[39][1]); } 越是不懂，越是要努力，加油。