Read Dynamic Programming intro first.
Please, read till the end, as this problem has a solution better than dp
Given an array of non-negative integers, 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.
Source code for this post available @github as maven based java project.
- build brute force recursive solution
- get surprised how slow it is and figure out why
- improve solution with memoization
- convert to “true” dynamic-programming bottom-up solution
- bonus step
Brute force solution
Recursion is a good starting point for brute force solution. If we are in position i, we know which positions to the right are reachable with one additional jump. Same rule applies to those right positions as well.
Running the code on small input works, but with longer array there is significant delay. After tracing the code, it’s easy to see that we call jump(array, index) many times for the same value of index. Caching should help us.
Top-down with memoization
As usual, the only change we made is to have a cache and use that cache instead of recalculation information already known.
Tracing how the cache is filled in, we can replicate the process by bottom up approach. Last element of the cache is zero - this is our destination. Bottom up algorithm fills the cache in right-to-left direction, using data calculated earlier. And the result is in cache.
This solution works. But check out test cases. It’s kind of slow for longer inputs. The reason is in O(n^2) running time for DP algorithm (you should make small change to the code from above to guarantee this estimate).
DP is not always the best solution
DP is amazing method for solving specific problems. But the downside is that DP is an exchange of memory-to-time; and DP does not make any other optimizations.
This specific problem is solvable in linear time; by tracking longest reachable element and making smart decision when we increase number of steps.
Bottom line: DP works well for this problem, comparing to brute force solution. But it always possible that more optimal approaches exist.