Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

自己的超时程序：

 1 public class Solution {
 2     private static int[]db;
 3     public static int climbStairs(int n) {
 4         db=new int[n+1];
 5         F(0,n);
 6         return db[n];
 7     }
 8     public static void F(int i,int n){
 9     db[i]++;
10     if(i>=n){return;}
11     F(i+1,n);
12     if(i>=n-1){return;}
13     F(i+2,n);
14     }
15     public static void main(String[]args){
16     System.out.println(climbStairs(44));
17     }
18 }

斐波那契数列求解：

 1 public int climbStairs(int n) {
 2     // bottom cases
 3     if(n <= 0) return 0;
 4     if(n == 1) return 1;
 5     if(n == 2) return 2;
 6 
 7     int one_step_before = 1;
 8     int two_steps_before = 2;
 9     int all_ways = 0;
10 
11     for(int i=2; i<n; i++){
12         all_ways = one_step_before + two_steps_before;
13         one_step_before = two_steps_before;
14         two_steps_before = all_ways;
15     }
16     return all_ways;
17 }

动态规划求解：

 1 public int climbStairs(int n) {
 2         int[] tmp = new int[n];
 3         if (n < 2){
 4             return 1;
 5         }
 6         tmp[0] = 1;
 7         tmp[1] = 2;
 8         for (int i = 2; i < n; i++){
 9             tmp[i] = tmp[i-1] + tmp[i-2];
10         }
11         return tmp[n-1];
12     }