/**
 *	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?
 *
 *	
 *	Author: matao
 *  
 * 	假设n级台阶共An中走法，则：
 *	n = 1时，A1 = 1;  (走1级)
 *  n = 2时，A2 = 2;  (走2个一级或走1个两级)
 *	所以n级台阶，可以走n-1级后再走1级 或 走n-2级后再走2级
 *	An ＝ An-1 + An-2;
 *	1 2 3 5 8...
 */

public class ClimbingStairs {
	// Recursion
	public static int climbStairs1(int n) {
		if(n == 1)
			return 1;
		if(n == 2)
			return 2;
		return climbStairs1(n-1) + climbStairs1(n-2);
    }

    // None-Recursion
    public static int climbStairs2(int n) {
    	if(n == 1)
    		return 1;
    	if(n == 2)
    		return 2;
    	int a = 1, b = 2, sum = 0;
    	for(int i = 3; i <= n; i++) {
    		sum = a+b;
    		a = b;
    		b = sum;
    	}
    	return sum;
    }

    public static void main(String[] args) {
    	System.out.println(climbStairs1(3));
    	System.out.println(climbStairs1(4));
    	System.out.println(climbStairs1(5));
    	System.out.println(climbStairs1(10));

    	System.out.println(climbStairs2(3));
    	System.out.println(climbStairs2(4));
    	System.out.println(climbStairs2(5));
    	System.out.println(climbStairs2(10));
    }
}
@@ -561,22 +561,27 @@
  // 
-None-Recursion
+Dynamic Programming
 %0A   
@@ -635,88 +635,95 @@
 f(n 
-=
+%3C
 = 1)
+ %7B
 %0A    
-%09%09
+        
 return 
-1
+n
 ;%0A    
-%09if(n == 2)%0A    %09%09return 2;%0A
+    %7D%0A    
     
-%09
 int 
-a
+pre
  = 1, 
-b = 2, sum
+ppre = 1;%0A        int curr
  = 0
@@ -728,17 +728,20 @@
  0;%0A    
-%09
+    
 for(int 
@@ -744,17 +744,17 @@
 int i = 
-3
+2
 ; i %3C= n
@@ -770,71 +770,112 @@
     
+ 
-%09%09sum = a+b;%0A    %09%09a = b;%0A    %09%09b = sum
+       curr = pre + ppre;%0A            ppre = pre;%0A            pre = curr
 ;%0A    
-%09
+    
 %7D%0A    
+ 
-%09
+   
 return 
-sum
+curr
 ;%0A  

optimize Climbing Stairs solution