C++ 16ms DP very intuitive, easy to understand solution


  • 1
    Q

    we start from the last pos, push it into a path buffer. Then we move to towards the begin of the array, put the pos that can reach the end of the path buffer. However, if we find that the new position can reach one pos further, we pop out the back of the path buffer, and test again, until we can reach the new back but not further.
    at the end the lenght of the buffer -1 is the path length.

    class Solution {
    public:
        int jump(vector<int>& nums) {
            int n = nums.size();
            vector<int> path;
            path.push_back(n-1);
            for(int i = n-2; i >=0; --i) {
               if(i+nums[i] >= path.back()) {
                   int sz = path.size();
                    while(sz-2 >= 0 && i + nums[i] >= path[sz-2]) {  //can reach one node further
                         path.pop_back();
                         --sz;
                    }
                    path.push_back(i);
               }
            }
            return path.size()-1;
        }
    };

Log in to reply
 

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