**Solution**

**Jump Game II** https://leetcode.com/problems/jump-game-ii/

**Dynamic Programming With Memoization**

- Sketch the recursion tree and implement the simple solution
- Base case: i == N-1, return 0. i > N-1, return float('inf')
- Recurse through all possible jumps from index i and find the minimum
- Use a cache to memoize
- This solution gives you a run time error: maximum recursion depth exceeded while calling a Py object!
- Time Complexity: O(N^2). Also Space complexity: O(N).

```
from collections import defaultdict
class Solution(object):
def helper(self, i, nums, cache):
if i == len(nums)-1:
return 0
elif i > len(nums)-1:
return float('inf')
elif i in cache:
return cache[i]
else:
cache[i] = float('inf')
for j in range(1, nums[i]+1):
cache[i] = min(cache[i], self.helper(i+j, nums, cache)+1)
return cache[i]
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cache = defaultdict(int)
return self.helper(0, nums, cache)
```

**Dynamic Programming With Cache**

- What is minimum cost to reach index i? Minimum cost to reach index 0 is 0.
- For indexi, lets find all indices j less than i. Now we can take a jump from index j if and only if (i-j)<=nums[j].
- Time Complexity: O(N^2). Also Space complexity: O(N).
- This solution gives a TLE

```
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cache = [float('inf')]*len(nums)
cache[0] = 0
for i in range(1, len(nums)):
for j in range(i):
if i - j <= nums[j]: # Can I take a jump from position j and reach i?
cache[i] = min(cache[i], cache[j] + 1)
return cache[-1]
```

**BFS Solution to Find the Minimum Jump**

- Model it like graph search problem and apply BFS to solve it
- Even this method gives TLE since it is N^2 solution.

```
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
q, levels = [0], -1
while len(q):
levels, new_level= levels + 1, []
for x in q:
for j in range(1, nums[x]+1):
if x + j == len(nums)-1:
return levels + 1
elif x + j < len(nums)-1:
new_level.append(x+j)
else:
break
q = new_level
return levels
```

**Greedy Approach which uses "Ladder Idea from Ideserve"**

- https://www.youtube.com/playlist?list=PLamzFoFxwoNgG0Q5rqfTY6ovWSTAC9mbz
- The invariant is that at a start index, we already know the maximum jump index that can be reached.
- We therefore move from index start to current_max_index and test whether we can reach further than current_max_index. Infact, we try to be greedy - we want to pick the next start point which would make us reach the farthest from current_max_index.
- Once we update the next start point, we recognize that we took a single jump.
- Take special note of initial conditions: current_max_index, start, jumps = 0, 0, 0. This initialization helps us to tackle cases likes nums =[1]. Other when length of nums is more than 1, the first jump takes us to start index 0 and sets current_max_index to nums[0].

```
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
current_max_index, start, jumps = 0, 0, 0
while start < len(nums):
if current_max_index >= len(nums)-1:
return jumps
for i in range(start, current_max_index+1):
if nums[i] + i > current_max_index:
start, current_max_index = i, nums[i]+i
jumps += 1
```