c++ dp


  • 0
    B
    
    int jump(vector<int> &nums) {
        vector<int> visited(nums.size(), -1);
        function<int(int)> jumpAt = [&](int startingPos) {
            if (startingPos >= nums.size() - 1) {
                return 0;
            }
            int &jumps = visited[startingPos];
            if (jumps != -1) return jumps;
            int canJump = nums[startingPos];
            int minJumps = INT32_MAX - 1;
            for (int i = canJump; i > 0; --i) {
                if (canJump == i or nums[startingPos + i] > canJump - i) {
                    minJumps = min(minJumps, jumpAt(startingPos + i) + 1);
                }
            }
            return jumps = minJumps;
        };
        return jumpAt(0);
    }
    

Log in to reply
 

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