Dynamic Programming Solution Using Java


  • 9
    H
    /*
     * 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];
        }

  • 0
    C

    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);
        
            }
        }
    

  • 0
    Z

    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.


  • 0
    J

    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.


  • 0

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


Log in to reply
 

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