Algorithm Puzzles ~~everyday~~ ~~every week~~ sometimes: Jump Game II

## Puzzle

Puzzle from leetcode:

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

## Solution

### First Came Solution: List + DP

My first came out solution is use list + dynamic programing:

1 | class Solution: |

It’s quite straight forward that use dp[n] stands for index we can reach at n jumps, so we can base on states in previous to calculate next index. It can work if input list is small, but it will hit “Time Limit Exceeded” error when list getting bigger.

### Optimized Solution: Set + DP

My optimized solution is using set instead of list - which can prevent duplicated calculation.

What’s more, since we only care about dp[n] and dp[n-1], there is no need to store dp[0]..dp[n-2] as well.

1 | class Solution: |

But the result of this solution is still not good enough…

### Greedy

Since we only care about minimal jumps to destination, we can use greedy to solve it. Give an index, we can find the farthest index we can go in next jump:

1 | class Solution: |