题目描述 第39阶台阶 小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级! 站在台阶前，他突然又想着一个问题： 如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多 少种不同的上法呢？ 请你利用计算机的优势，帮助小明寻找答案。 要求提交的是一个整数。 注意：不要提交解答过程，或其它的辅助说明文字
思路：这题有2种方法，一种是dfs，一种是dp方法，dfs比较容易理解。 dp： 转移方程： dp[i][j] = dp[i-1][j^1] + dp[i-2][j^1].代表走到第i个台阶是j脚的方法数（j只有0和1,0代表左脚，1代表右脚） 值初始化： dp[1][0] =dp[2][0]=dp[2][1]=1;
dp
#include<stdio.h> int dp[40][2]; int main(){ dp[2][0] = dp[2][1] = dp[1][0] = 1; for(int i = 3;i<=39;i++) for(int j = 0;j<=1;j++) dp[i][j] = dp[i-1][j^1] + dp[i-2][j^1]; printf("%d\n",dp[39][1]); return 0; }dfs
#include<stdio.h> int dfs(int step,int foot){ if(step==39&&!(foot&1)){//步数为39，且是右脚 return 1; }else if(step>39)return 0; return dfs(step+1,foot+1)+dfs(step+2,foot+1); } int main(){ printf("%d\n",dfs(0,0)); return 0; }