My DP solution in C++ with explanation


  • 15
    V
     int climbStairs(int n) 
    {
         vector<int> steps(n,0);
         steps[0]=1;
         steps[1]=2;
         for(int i=2;i<n;i++)
         {
             steps[i]=steps[i-2]+steps[i-1];
         }
         return steps[n-1];
     }
    

    Array 'steps' stands for how many distinct ways to climb to each level (index from 0, so 0 means level 1, 1 means level 2 and so on.... ). It's trivial to know it has 1 distinct way to climb to stair 1 , and 2 distinct ways to climb to stair 2 . For stair level n (n>=3) , you can either (1) climb to stair n-2 , and climb 2 more steps to reach n , OR (2) climb to stair n-1, and climb 1 more step to reach n. That said , steps[n]=steps[n-1]+steps[n-2]. In another word, the number of distinct ways to reach level n is the sum of number of distinct ways to reach level n-1 and n-2.


  • 2
    V

    in stead of using vector/array steps[] , which costs O(n) space, you can also just use two variables in the loop to get the final result. But i find it's much clearer to show the thoughts behind it by using the vector/array steps[].


  • 0

    then the answer will be like orientallee's


  • 0

    Thank you for your sharing ,and the thoughts is really be much clearer by the use of the vector, but we can save some space if use the vector like this:vector<int> steps(n-1,0);


  • 0
    A

    Hi, thanks! It is very clear and helpful. I believe I use the recursion with the same logic, but it gives me time exceeded when input is 44, can anyone help?

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


  • 3
    V

    Because you were doing recursion without memorization, then you end up recalculating lots of stuff . e.g: when calculating f(44)=f(43)+f(42), you first calculate f(43) , then you calculate f(42), while f(42) is already available when calculating f(43). So... use a cache to store all your intermediate results and return the result immediately if it's already calculated .

    class Solution {
    public:
        unordered_map<int,int> cache;
        int climbStairs(int n) {
             if(cache.find(n)!=cache.end()) return cache[n];
             int result = 0;
             if (n == 0) result = 0;
             else if (n == 1) result= 1; 
             else if (n == 2) result = 2; 
             else result = climbStairs(n-1) + climbStairs(n-2); 
             
             cache[n]=result;
             return result;
        }
    };
    

  • 0
    A

    Very clearly explained! Thank you! Now I see, next time I need to be more careful on what steps are being done over and over. Much appreciated!


  • 0

    So DP is like a method = recursion + memorization, right?


  • 1
    V

    not always. To my understanding the 'top down' approach usually involves recursion+ memorization, while "bottom up" usually does not. There are loads of related discussions online and you can take a look.


  • 0
    X

    @Alex.Wang.9 because it cost too much time.


  • 0
    T

    @vogelkaka said in My DP solution in C++ with explanation:

    f(cache.find(n)!=cache.end()) return cache[n];
    int result = 0;
    if (n == 0) result = 0;
    else if (n == 1) result= 1;
    else if (n == 2) result = 2;
    else result = climbStairs(n-1) + climbStairs(n-2);

         cache[n]=result;
         return result;
    }
    

    I had same doubts with @Alex-Wang-9, thanks for the explanation.
    By the way: this solution has very clear explanation of dynamic programming:
    https://leetcode.com/problems/jump-game/solution/


  • 0
    S

    Same idea here!

    class Solution {
    public:
        int climbStairs(int n) {
            if ( n == 0 ) return 0;
            else if ( n == 1 ) return 1;
            else if ( n == 2 ) return 2;
            
            vector<int> ways(n+1, 0);
            ways[1] = 1; ways[2] = 2;
            for ( int i = 3; i <= n; i++ ) {
                ways[i] = ways[i-1] + ways[i-2];
            }
            
            return ways[n];
        }
    

Log in to reply
 

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