Deadly simple C++ 12ms DP (greedy) solution, 5 active lines, O(1) space, O(N) time


  • 2
    X

    Since we do not need to determine the optimal path or anything, we just keep track of whether we can move one step forward, renewing the "reserved jumps" number if necessary.

    bool canJump(vector<int>& nums) {
        if(nums.empty()) return true;
        int m = nums[0];
        for(auto i = 1; i < nums.size(); ++i)
        {
            if(m <= 0) return false;
            m = max(m - 1, nums[i]);
        }
        return true;
    }

  • 0
    J

    Is it DP? I think this is greedy.


  • 0
    X

    Yes, you're right - however greedy approach is just a special case of DP, so I think both namings are correct. I'm not sure why this solution has got a down vote though ( is it <= 0 instead of == 0, or 'auto' for size_t?).


Log in to reply
 

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