Share my greedy solution and proof for greedy choice property


  • 1
    Z

    I first come up with a dp solution but after some analysis, I figured out it can be reduced to a greedy problem. My idea is borrowed from one of the great top solutions (https://discuss.leetcode.com/topic/28470/concise-o-n-one-loop-java-solution-based-on-greedy)

    However, it seems no one gave a formal proof that it can be solved by greedy strategy. Here is my proof:

    Greedy choice property
    For position t, there exists an optimal solution in which the minimum steps is obtained by jumping from position i, where i + nums[i] == t.

    Proof by contradiction:
    1)Suppose there exist a position j, i < j, and j + nums[j] >= t, such that the minimum steps of jumping from j to t will lower than that of jumping from i to t.
    2) Let minSteps(k) denotes minimum steps at position k;
    3) Such that we have i < j < t and minSteps(i) > minSteps(j) obtained from step 1)
    4) Because t - i > t - j, it implies that nums[i] > nums[j]. Therefore, minSteps(i) <= minSteps(j), which contradicts the supposition that minSteps(i) > minSteps(j)

    public class Solution {
        public int jump(int[] nums) {
            if(nums.length <= 1) return 0;
            int minSteps = 0;
            int upperBound = 0;
            int reachable = 0;
            
            for(int i = 0; i < nums.length; i++){
                reachable = Math.max(i + nums[i], reachable);
                if(i > upperBound){
                    minSteps++;
                    upperBound = reachable;
                    if(upperBound >= nums.length - 1)
                        return minSteps;
                }
            }
            return minSteps;
        }
    }
    

Log in to reply
 

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