题目
- 给定一个非负的数组，初始化位置在数组的0值处
- 每个元素代表了你能所能从当前位置调到的最远处
- 你的目标是通过最少次数的jump到达数组的末尾
- 假设你始终可以从头跳到最后，即结果永远存在
解法1（动态规划，死解，超时）
- 考虑动态规划解法，动态规划三要素，最优子结构，状态转移方程和边界条件
- 首先我们考虑最优子结构：假设我们要求的结果F(n)表示下标为n的最小次数，那么根据条件F(n) = min{F(k)} + 1,其中k需要满足条件k+nums[k] >= n。
- 同时上述方程也是状态转移方程，其边界条件为当n为0时，F(0) = 0;
- 考虑从下至上合并的动态规划思想，我们申明一个dp数组,全部装填最大数字，表示数组中任意一个下标的最小次数
- 外层从0开始遍历，用i表示，内层用j表示，从0开始到i遍历，上述状态转移方程转化为dp[i] = min{dp[j]} + 1，如果符合条件j+nums[j] >= i 那么此时就更新dp[i] = min{dp[i], dp[j]}
- 时间复杂度是O(n^2),空间复杂度O(n)
- leetcode通过超时
源代码实现
class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int[] dp = new int[nums.length];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (j + nums[j] >= i) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
return dp[nums.length-1];
}
}
大牛解法
- 考虑需要找的最少跳数，扫描数组，以确定当前最远能覆盖的节点，放入curr。然后继续扫描，直到当前的路程超过了上一次算出的覆盖范围，那么更新覆盖范围，同时更新条数，我们是经过了多一跳才能继续前进的。争取每条最远的greedy算法
- 举例，题目中[2,3,1,4]初始状态cur表示最远能覆盖的地方，红色表示，last表示已覆盖的地方，箭头表示，都指向某一个元素
初始化状态 - 接下来，第一元素告诉cur,最远可以走2步，如图中所示：
第一次 - 下一循环中，i指向1，发现i小于last能到的范围，于是更新last，步数ret+1,同时需要更新cur,因为最远距离发现了
第二次 - 接下来，i继续前进，发现i在当前的势力范围内，无须更新last和步数ret，更新cur
第三次 - i继续前进，接下来发现超过当前势力范围，更新last和步数。cur已然最大了
第四次 - 最后，i到达最后一个元素，已然在势力范围内，遍历完成，返回ret
第五次
源代码
class Solution {
public int jump(int[] nums) {
int result = 0;
int last = 0;
int curr = 0;
for (int i = 0; i < nums.length; i++) {
if (i > last) {
last = curr;
result++;
}
curr = Math.max(curr, i+nums[i]);
}
return result;
}
}
参考链接
https://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
