1、问题描述
有一楼梯共 M 级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第 M 级，共有多少种走法？
输入输出描述 Input 输入数据首先包含一个整数 N，表示测试实例的个数，然后是 N 行数据，每行包含一个整数 M（1<=M<=40）, 表示楼梯的级数。Output 对于每个测试实例，请输出不同走法的数量示例：
Sample Input223Sample Output12
2、思路分析
利用动态规划（DP，dynamic programming）思想，简单来说：大事化小小事化了
假设 10 级，考虑只差最后一步到 10 级，一步走 1 阶或 2 阶，只有两种可能：到 9 阶和到 8 阶。如果到 9 阶的走法有 X 种，到 8 阶的走法有 Y 种，那么，总走法 =X+Y。即：F(10)=F(9)+F(8) 同理，F(9)=F(8)+F(7)，F(8)=F(7)+F(6)，这样问题可以从 10 阶到 [9 和 8] 阶，再到 [9 和 8] 拆开的阶，这样往下，分阶段将问题简化。
寻找基准或者初始解：当为 F(2) 和 F(1) 时，前者有两种走法（1+1，2），后者有一种走法（1）。即：①F(2)=2，F(1)=1。再加上②F(10)=F(9)+F(8)，
得到三个动态规划的概念：【最优子结构】：F(9) 和 F(8)，是 F(10) 的最优子结构【边界】：F(1) 和 F(2) 是问题的边界，无法再简化 / 拆解【状态转移方程】：F(10)=F(9)+F(8)，上下阶段的关系
递归公式：F(n)=F(n-1)+F(n-2)，实为斐波那契数列的递归公式。
3、程序实现
首先用递归进行实现，与动态规划做比较。前者代码简洁，但执行效率不如后者。
1）递归
int getWays(int n){
if(n<1) return 0;
if(n==1) return 1;
if(n==2) return 2;
return getWays(n-1)+getWays(n-2)
}
2）动态规划
从底到上推导：F(1)=1，F(2)=2，F(3)=F(2)+F(1)=1+2F(4)=F(3)+F(2)=3+ 2 每次迭代，只保留之前的两个状态，即可推导新的状态。
源程序：
import java.util.Scanner;
/**
* Input: 输入数据首先包含一个整数 N，表示测试实例的个数，然后是 N 行数据，每行包含一个整数 M（1<=M<=40）, 表示楼梯的级数。
* Output: 对于每个测试实例，请输出不同走法的数量
*/
public class DPSumsung {
public static int getWays(int n) {
if(n<1) return 0;
if(n==1) return 1;
if(n==2) return 2;
int a=1;
int b=2;
int next=0;
for(int i=3;i<=n;i++) {
next=a+b;
a=b;
b=next;
}
return next;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int count=sc.nextInt();
int[] ways=new int[count];
int i=0;
int n=sc.nextInt();
while(n>=1&&n<=40) {
ways[i++]=DPSumsung.getWays(n);
if(i>=count)
break;
n=sc.nextInt();
}
for(int temp:ways) {
System.out.println(temp);
}
sc.close();
}
}
4、算法分析
时间复杂度为 O(N)，空间复杂度为 O(1)。