题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数
1 /* 2 * 方法一：递归法 3 * 递归把握:终止条件、递归方程和退出形式 4 * 1、递归方程：F(N)=F(N-1)+F(N-2) 5 * 2、终止条件：F(1)=1,F(2)=2; 6 * 3、退出形式： 7 */ 8 public int climbStairs1(int n) { 9 if(n < 1) { 10 throw new IllegalArgumentException("非法参数输入"); 11 } 12 if(n == 1){ 13 return 1; 14 }else if(n == 2) { 15 return 2; 16 }else { 17 return climbStairs1(n-1) + climbStairs1(n-2); 18 } 19 } 20 21 /* 22 * 方法二：动态规划 23 * 动态规划三要素：最优子结构(递归方程)、边界条件(终止条件)和状态转移方程(前两者总结) 24 */ 25 public int climbStairs21(int n) { 26 if(n < 1) { 27 throw new IllegalArgumentException("非法参数输入"); 28 } 29 if(n == 1) { 30 return 1; 31 }else if(n == 2) { 32 return 2; 33 }else { 34 int a = 1; 35 int b = 2; 36 int result = 0; 37 for(int i=3; i<=n; i++) { 38 result = a + b; 39 a = b; 40 b = result; 41 } 42 return result; 43 } 44 } 45 //动态规划二 46 public int climbStairs22 (int n) { 47 if(n < 1) { 48 throw new IllegalArgumentException("参数输入错误"); 49 } 50 if(n == 1) { //防止n=1时results数组越界 51 return 1; 52 } 53 int[] results = new int[n]; 54 results[0] = 1; 55 results[1] = 2; 56 for(int i=2; i<n; i++) { 57 results[i] = results[i-1] + results[i-2]; 58 } 59 return results[n-1]; 60 } 61 62 /* 63 * 方法三：记忆法(备忘录法)，递归法的改进 64 */ 65 private Map<Integer, Integer> map = new HashMap<>(); 66 public int climbStairs3(int n) { 67 if(n < 1) { 68 throw new IllegalArgumentException("参数输入错误"); 69 } 70 if(n == 1) { 71 return 1; 72 } 73 if(n == 2) { 74 return 2; 75 } 76 if(map.containsKey(n)) { 77 return map.get(n); 78 }else { 79 int result = climbStairs3(n-1) + climbStairs3(n-2); 80 map.put(n, result); 81 return result; 82 } 83 }