Dynamic Programming Solution Using Java

• ``````/*
* 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(i-1) + W(i-2)
* where W(i-1) is when the ith stair is as a single step
* and W(i-2) 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[i-1] + tmp[i-2];
}
return tmp[n-1];
}``````

• why my java recursive code has "Status: Time Limit Exceeded" error? is it same as OP's array code?

``````public class Solution {
public int climbStairs(int n) {
if (n==1) return 1;
else if (n==2) return 2;
else return  climbStairs(n-1)+climbStairs(n-2);

}
}
``````

• Recursive method usually takes much longer time than the loop.
It has to call itself multiple times. There will be a very large call and return stack when the input number is big.

• The regular recursion method will call climbStairs(n) for the same n several times. You can store the results for each n in a collection, and reuse them afterwards. That will be an dynamic programming recursion.

• @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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.