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