LeetCode Q45: Jump Game II

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.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

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

I am always confuse whether to use DP when get a question like this. I ask myself what the subproblem is and how the solution structures of subproblems overlapping each other. For this question, the definition of the subproblems is  steps[i] = min{1+steps[j]}, if nums[j] can reach i, j

	class Solution {
	public:
	int jump(vector<int>& nums) {
	//Build a map which shows the furthest previous node that can reach current position
	//Step1, forward pass to get the furthest place each node can reach.
	vector<int> marker(nums.size(), nums.size());
	int smallestIdx=0;
	for(int i=0; i<nums.size(); ++i){
	if(i<=marker[min(i+nums[i], int(nums.size())-1)]){
	marker[min(i+nums[i], int(nums.size())-1)]=i;
	smallestIdx=i;
	}
	}
	//Step2, fill up all empty entries.
	smallestIdx=marker[nums.size()-1];
	for(int i=nums.size()-1; i>=0; i--){
	if(marker[i]<=smallestIdx){
	smallestIdx=marker[i];
	}else{
	marker[i]=smallestIdx;
	}
	}
	//Trace back to finish hop
	int steps=0;
	int prePos=marker[nums.size()-1];
	int curPos=nums.size()-1;
	while(curPos!=0){
	curPos=prePos;
	prePos=marker[curPos];
	steps++;
	}
	return steps;
	}
	};

view raw Q45JumpGameII.cpp hosted with ❤ by GitHub

A neater solution I like is given in Leetcode forum:
https://leetcode.com/discuss/45992/10-lines-c-16ms-python-bfs-solutions-with-explanations

The explanation given by author is in below:

This problem has a nice BFS structure. Let's illustrate it using the example nums = [2, 3, 1, 1, 4] in the problem statement. We are initially at position 0. Then we can move at most nums[0]steps from it. So, after one move, we may reach nums[1] = 3 or nums[2] = 1. So these nodes are reachable in 1 move. From these nodes, we can further move to nums[3] = 1 and nums[4] = 4. Now you can see that the target nums[4] = 4 is reachable in 2 moves.

Putting these into codes, we keep two pointers start and end that record the current range of the starting nodes. Each time after we make a move, update start to be end + 1 and end to be the farthest index that can be reached in 1 move from the current [start, end].

To get an accepted solution, it is important to handle all the edge cases. And the following codes handle all of them in a unified way without using the unclean if statements :-)

	class Solution {
	public:
	int jump(vector<int>& nums) {
	int n = nums.size(), step = 0, start = 0, end = 0;
	while (end < n - 1) {
	step++;
	int maxend = end + 1;
	for (int i = start; i <= end; i++) {
	if (i + nums[i] >= n - 1) return step;
	maxend = max(maxend, i + nums[i]);
	}
	start = end + 1;
	end = maxend;
	}
	return step;
	}
	};

view raw Q45Others.cpp hosted with ❤ by GitHub