C++ DP top-down with explaination


  • 0
    V
    class Solution {
        /*top down approach: we use memoization array m where m[i] indicates cost to
        reach at end if we take jump from ith step. Base case is when you're at last
        step, you take jump and pay it's cost. We start from last step and move back
        to start, finally return min(m[0], m[1]) since we can choose to start from 
        any of those 2 steps.
        */
    public:
        int minCostClimbingStairs(vector<int>& cost) {
            vector<int> m(cost.size(), 0);
            m[cost.size() - 1] = cost[cost.size() - 1];
            for (int i = cost.size() - 2; i >= 0; i--)
                m[i] = cost[i] + min(m[i+1], i+2 < m.size() ? m[i+2] : 0);
            return min(m[0], m[1]);
        }
    };
    

Log in to reply
 

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