LintCode Climbing Stairs

Given an example n=3 , 1+1+1=2+1=1+2=3

return 3

For the problem, try to think about it in this way.

Firstly, we define the problem of DP(n) as the ways of approaching to n stairs. 

The problem of DP(n) depends on DP(n-1) and DP(n-2). Then the DP(n) = DP(n-1) + DP(n-2). Because there is two possibilities for DP(n) happen due to the rule that either it is accomplished by step 1 or step 2 stairs before approaching to n.

Initialize the DP(0) =1 and DP(1) = 1.

Solve problem DP(n)

 1 public class Solution {
 2     /**
 3      * @param n: An integer
 4      * @return: An integer
 5      */
 6     public int climbStairs(int n) {
 7         // write your code here
 8         if (n <= 1) {
 9             return 1;
10         }
11         int last = 1, lastlast = 1;
12         int now = 0;
13         for (int i = 1; i < n; i++) {
14             now = last + lastlast;
15             lastlast = last;
16             last = now;
17         }
18         return now;
19     }
20 }

Then this problem is a fibonacci sequence