Jump Game
Question (LC.55)
Given an array of non-negative integers, each element represents the max length you can jump at that position. Starting from the first index, can you reach the end?
Example
I: A = [2,3,1,1,4]
O: True
I: A = [3,2,1,0,4]
O: there is a 0 on the index 3 and no way to jump over it. FalseAnalysis
First thing to do is drawing out the jump DAG. Having a concrete picture is much easier way to think than looking at the numbers themselves. Essentially, we want to know whether there is a path from the first node to the last node. Intuitively, we can use DFS to test if the last node is reachable from the first node.
DFS Approach
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return true;
}
int[] flag = new int[1];
jumpHelper(nums, 0, flag);
return flag[0] == 1;
}
private void jumpHelper(int[] nums, int currentPos, int[] flag) {
if (flag[0] == 1) {
return;
}
if (currentPos == nums.length - 1) {
flag[0] = 1;
return;
}
for (int i = 1; i <= nums[currentPos]; i++) {
jumpHelper(nums, currentPos + i, flag);
}
}DP Approach
Then we observe there can overlapping paths. For example, if we already know a path is not leading to the destination, we don't have to recursively visit it again.
5-->1-->2-->0-->0-->1
memo[2]1. Define (optimal) subproblem
Jump(i) = can you jump to index i from index 0
2. Solve by prefix
for j from i-1 to 0
if Jump(j) and nums(j) >= i-j
Jump(i) = true
(we can break as long as we find one true Jump(j))
3. Init base
Jump(0) = true
4. Topo order
for i from 1 to n-1
5. Final answer
Jump(n-1)DP Code
public boolean canJump(int[] nums) {
// create memo
int n = nums.length;
boolean[] memo = new boolean[n];
// init base
memo[0] = true;
// topo order
for (int i = 1; i <= n - 1; i++) {
for (int j = i - 1; j >= 0; j--) {
if (memo[j] && nums[j] >= i - j) {
memo[i] = true;
break;
}
}
}
// final answer
return memo[n - 1];
}Greedy Approach
Jump Game II (LC.45)
The objective now is to minimize the number of steps to reach the last index.
Example
I: nums = [2,3,1,1,4]
O: 2-->3-->4 = 2 jumpsWhat if there's a gap? For instance [2,1,0,0,5]. Assume that you can always reach the last index.
Analysis
Obviously, we can do an exhaustive search from the last index to find all possible paths and maintain a global min. But then many paths would be revisited many times. We can use memoization or tabulation to avoid recomputing the same path.
DP Approach
1. Optimal subproblem
jp(i) = minimum number of jumps to reach index i
2. Solve by prefix
for j from i to 0
if reachable: jp(i) = Math.min(jp(i), jp(j) + 1)
3. Topo order
for i from 1 to n-1
4. Base case
all init to unreachable
jp(0) = 1
5. Final answer
jp(n-1)DP Code
public int jump(int[] nums) {
int n = nums.length;
// create memo table
int[] jp = new int[n];
// init base case
jp[0] = 0; // don't count the first jump
for (int i = 1; i < n; i++) {
jp[i] = Integer.MAX_VALUE;
}
// topo order
for (int i = 1; i < n; i++) {
// recurrence
for (int j = i-1; j >= 0; j--) {
if (nums[j] + j >= i) { // reachable
jp[i] = Math.min(jp[i], jp[j] + 1);
}
}
}
// final answer
return jp[n-1];
}Time & Space Complexity
The DP solution gives O(n^2) time and uses O(n) extra space. However, it results in time limit exceeded on LC. This begs for another approach that is linear time.
Greedy Approach
Exchange argument
Switch to the pos before and can jump to the current pos
Keep the rest of the solution optimal
Search backward from current pos to find the leftest pos that can jump to the current position then look left again from that leftest position
def jump(self, nums: List[int]) -> int:
n = len(nums)
if n <= 1:
return 0
current_index = n - 1
steps = 0
while current_index > 0:
for i in range(current_index - 1, -1, -1):
if nums[i] + i >= current_index:
left_most_index = i
current_index = left_most_index
steps += 1
return steps Time O(n^2) Space O(1)
Conclusion
We can certainly use memoization for any DP question. But if the we can easily figure out the topological ordering, then we can also do tabulation which saves the call stack.
Last updated