/*
* Ideas:
* Use Dynamic Programming,
* for each step, the stair could ether combine with the previous one or as a single step.
* Ways to climb to ith stair is W(i) = W(i1) + W(i2)
* where W(i1) is when the ith stair is as a single step
* and W(i2) is when the ith stair is paired with the previous one.
*/
public int climbStairs(int n) {
int[] tmp = new int[n];
if (n < 2){
return 1;
}
tmp[0] = 1;
tmp[1] = 2;
for (int i = 2; i < n; i++){
tmp[i] = tmp[i1] + tmp[i2];
}
return tmp[n1];
}
Dynamic Programming Solution Using Java


@houzhaowei I think it should be
return n
for the corner case when n is less or equal to 2. For n = 2, it could be two of one step OR one of two steps.