# Share my greedy solution and proof for greedy choice property

• 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`.

`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;
}
}
``````

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