LeetCode Jump Game II

LeetCode 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.


上一题是问能否跳到数组右边,本题问最少需要多少跳能跳到数组右边,第一反应是DP。

设dp[i]表示从位置i跳到数组右边最少需要的跳数,则dp[n-1]=0,dp[0]就是最终结果。此时我们需要从数组右边往左边遍历,假设dp[i+1,...,n-1]都求出来了,现在要求dp[i]。站在位置i,我们最远能跳到i+A[i],所以我们就看看从i跳到哪个j\in[i,i+A[i]]能获得最少的跳数,从i跳到j需要增加一跳,所以递推式就是

dp[i]=min\{dp[j]+1\},\quad j\in[i+1,i+A[i]]

这种思路的代码如下:

class Solution {
public:
	int jump(vector<int>& nums) {
		int n = nums.size();
		if (n <= 1)return 0;
		int maxJump = n - 1;
		vector<int> dp(n, 0);
		for (int i = n - 2; i >= 0; --i) {
			int curMinJump = maxJump;
			for (int j = i + 1; j <= nums[i] + i&&j < n; ++j) {
				curMinJump = min(curMinJump, dp[j] + 1);
			}
			dp[i] = curMinJump;
		}
		return dp[0];
	}
};

可惜,本代码提交TLE,在最后一个大数据集上超时了。但是我还是觉得DP方法是一个基本法,而且如果要求出最小跳的路径,也很方便,如下代码,打印的时候,从pre[n-1]不断找前驱位置就好。

class Solution {
public:
	int jump(vector<int>& nums) {
		int n = nums.size();
		if (n <= 1)return 0;
		int maxJump = n - 1;
		vector<int> dp(n, 0), pre(n, 0);
		for (int i = n - 2; i >= 0; --i) {
			int curMinJump = maxJump, k = 0;
			for (int j = i + 1; j <= nums[i] + i&&j < n; ++j) {
				if (dp[j] + 1 < curMinJump) {
					curMinJump = dp[j] + 1;
					k = j;
				}
			}
			dp[i] = curMinJump;
			pre[k] = i; // 从i跳到k能获得最小跳数
		}
		return dp[0];
	}
};

讨论区看到一个O(n)的解法,很厉害。思路和上一题LeetCode Jump Game很类似,依旧维护一个当前能跳到的最远位置curFarthest,同时维护一个当前跳能跳到的范围[curBegin, curEnd],一旦i超过了curEnd,说明应该开启下一跳了,同时更新curFarthest。

这种算法的思路很巧妙,他不管你当前跳到底跳到哪里,只管你能够跳到的范围,一旦走出这个范围,就必须开启下一跳了。代码如下:

class Solution {
public:
	int jump(vector<int>& nums) {
		int jumps = 0, curEnd = 0, curFarthest = 0;
		for (int i = 0; i < nums.size() - 1; ++i) {
			curFarthest = max(curFarthest, i + nums[i]);
			if (i == curEnd) {
				curEnd = curFarthest;
				++jumps;
				if (curEnd >= nums.size() - 1)break;
			}
		}
		return jumps;
	}
};

本代码提交AC,用时22MS。第10行是增加的提前结束的代码。

参考:

Leave a Reply

Your email address will not be published. Required fields are marked *