Difference between DP and Greedy


  • 1
    H

    What is the difference between DP and Greedy? My observation is that Greedy directly compares the two indices by looking forward, while DP monitors the difference of two indices by looking backward.

    bool canJump(vector<int>& nums) {
    	int maxSteps=0; // maxSteps defines the maximum steps we just still jump at index i
    	for (int i=0; i<nums.size(); i++) {
    		maxSteps = max(maxSteps-1, nums[i]);
    		if (maxSteps == 0) return false;
    	}
    	return true;
    }

  • 0
    C

    It seems the code above has a small mistake, here is a revised version:

    bool canJump(vector<int>& nums) {
    int maxSteps=0; // maxSteps defines the maximum steps we just still jump at index i
    for (int i=0; i<nums.size(); i++) {
        maxSteps = max(maxSteps-1, nums[i]);
        if (maxSteps == 0 && i < nums.size()-1) return false;
    }
    return true;
    

    }


  • 0
    T

    It took me a minute to diff the two codes... caikehe added i < nums.size()-1 to the if


  • 0
    T

    What is the mistake? What input would fail?


Log in to reply
 

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