Jump games Greedy/DP

55. Jump Game

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int can_reach = 0;
        for (int i =0;i<=can_reach;++i){
            if (i==nums.size()-1)return true;
            can_reach = max(can_reach, i+nums[i]);
        }
        return false;
        
    }
};

45. Jump Game II

A naive solution got TLE. This solution has the complexity of O(N²) in the worst case.

class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        for (int i=nums.size()-2;i>=0;--i){
            int res = INT_MAX;
            for (int j=1; j<=nums[i];++j){
                if(i+j<nums.size()) res = min(res, dp[i+j]);
            }
            //cout<<dp[i]<<","<<res<<endl;
            dp[i] = res==INT_MAX? INT_MAX : res+1;
        }
    return dp[0];
    }
};

Using a map to optimize and the performance is even worst. TLE. The reason is the smaller DP value will be the right most positions. Those positions have a higher possibility as invalid positions as it is not easy to reach there from the current position

// time complexity O(n^2)
// space complexity O(n)
class Solution {
public:
    int jump(vector<int>& nums) {
        map<int, int> m;
        vector<int> dp(nums.size(), 0);
        m[0] = nums.size()-1;
        for (int i=nums.size()-2;i>=0;--i){
            int res = INT_MAX;
            for (auto &x:m){
                if (x.second<=i+nums[i]){
                    res = x.first;
                    break;
                    }
            }
            //cout<<dp[i]<<","<<res<<endl;
            dp[i] = res==INT_MAX? INT_MAX : res+1;
            m[dp[i]] = i;
        }
    return dp[0];
    }
};

The point is we want to get a minimum value from the dp[i+1] to dp[i+nums[i]]. If nums[i] is a fixed value, and we can use a priority queue, multiset, or monotonic queue to solve this problem. See HERE. However, nums[i] is dynamic. It makes this problem kind of hard.

We may think about using a segment tree to solve this problem as for the segment tree, the range max/min query will be O(log n). However, it is kind of overkill. Actually, we can use a greedy algorithm to solve this problem.

// time complexity O(n)
// space complexity O(1)
class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size()==1)return 0;
        int ret = 1, limit = nums[0], max_reachable_idx = nums[0];
        for (int i=0;i<nums.size();++i){
            if (i>limit){
                ret++;
                limit = max_reachable_idx;
            }
            max_reachable_idx = max(max_reachable_idx, i+nums[i]);
        }
        return ret;
    }   
};