算法：动态规划

题目：有一座高度是10阶的楼梯，从下往上走，没跨一步只能向上1级或者2级台阶。要求用程序求出一共有多少种走法。

F(1) = 1;
F(2) = 2;
F(n) = F(n-1)+F(n-2) (n>3)

解法一：递归求解

int getClimbingWays(int n) {
  if(n < 1){
    return 0;
  }
  if(n == 1){
    return 1;
  }
  if(n == 2){
    return 2;
  }
  return getClimbingWays(n-1)  + getClimbingWays(n-2);
}

解法二：备忘录算法

int getClimbingWays(int n, HashMap<Integer, Integer> map) {
  if(n < 1){
    return 0;
  }
  if(n == 1){
    return 1;
  }
  if(n == 2){
    return 2;
  }
  if(map.contains(n)){
    return map.get(n);
  }else{
    int value = getClimbingWays(n-1)  + getClimbingWays(n-2);
    map.put(n,value);
    return value;
  }
}
  

解法三：动态规划求解

int getClimbingWays(int n) {
  if(n < 1){
    return 0;
  }
  if(n == 1){
    return 1;
  }
  if(n == 2){
    return 2;
  }
  int a = 1;
  int b = 2;
  int temp = 0;
  for(int i=3; i<=n; i++){
    temp = a + b;
    a = b;
    b = temp;
  }
  return temp;
}

动态规划：
三个重要概念：【最优子结构】、【边界】、【状态转移公式】。