爬楼梯

public int climbStairs (int n) {
        // write code here
        // 斐波那契数列
        // 动态规划
        //if (n <= 3) {
        //    return n;
        //}
        //int dp[] = new int[n];
        //dp[0] = 1;
        //dp[1] = 2;
        //dp[2] = 3;
        //for (int i = 2; i < n; i++) {
        //    dp[i] = dp[i - 1] + dp[i - 2];
        //}
        //return dp[n-1];
        
        // 压缩状态
        int a = 0, b = 0, c = 1;
        for (int i = 0; i < n; i++) {
            a = b;
            b = c;
            c = a + b;
        }
        return c;
    }

public int climbStairs(int n) {
    int r[] = new int[n + 1];
    r[0] = 1;
    r[1] = 1;
    for (int i = 2; i <= n; i++) {
        r[i] = (r[i - 1] + r[i - 2]);
    }
    return r[n];
}

public class Solution {
    public int climbStairs(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        int a = 1;
        int b = 2;
        while (n-- > 2) {
            int tmp = b;
            b = a + b;
            a = tmp;
        }
        return b;
    }
}

public class Solution {
    public int climbStairs(int n) {
        if (n < 3) return n;
        int first = 1, second = 2;
        int result = 0;
        for (int i = 3; i <= n; i++) {
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }
}

public class Solution {
    public int climbStairs(int n) {
        if(n==1)return 1;
        if(n==2)return 2;
        int num[] = new int[n+1];
        num[1]=1;num[2]=2;
        for(int i = 3; i<=n; i++)
            num[i] = num[i-1]+num[i-2];        
        return num[n];
    }
}

public class Solution {
    public int climbStairs(int n) {
        int ppre = 0;
        int pre = 1;
		int cur = 0;
        while(n-- > 0) {
            cur = ppre + pre;
            ppre = pre;
            pre = cur;
        }
        return cur;
    }
}

The problem seems to be a dynamic programming one. Hint: the tag also suggests that!
Here are the steps to get the solution incrementally.

• Base cases:
  if n <= 0, then the number of ways should be zero.
  if n == 1, then there is only way to climb the stair.
  if n == 2, then there are two ways to climb the stairs. One solution is one step by another; the other one is two steps at one time.

• The key intuition to solve the problem is that given a number of stairs n, if we know the number ways to get to the points [n-1] and [n-2] respectively, denoted as n1 and n2 , then the total ways to get to the point [n] is n1 + n2. Because from the [n-1] point, we can take one single step to reach [n]. And from the [n-2] point, we could take two steps to get there. There is NO overlapping between these two solution sets, because we differ in the final step.

Now given the above intuition, one can construct an array where each node stores the solution for each number n. Or if we look at it closer, it is clear that this is basically a fibonacci number, with the starting numbers as 1 and 2, instead of 1 and 1.

The implementation in Java as follows:

public int climbStairs(int n) { // base cases if(n <= 0) return 0; if(n == 1) return 1; if(n == 2) return 2; int one_step_before = 2; int two_steps_before = 1; int all_ways = 0; for(int i=2; i<n; i++){
    	all_ways = one_step_before + two_steps_before;
    	two_steps_before = one_step_before;
        one_step_before = all_ways;
    } return all_ways;
}

public int climbStairs(int n) {
		int[] dp = new int[n + 1];
		dp[0] = 1;
		dp[1] = 1;
		for (int i = 2; i < dp.length; i ++ ) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
	}