LintCode 117. Jump Game II 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/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.
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.)
解题思路
题目求到数组最后一个位置的最小跳跃数。
求极小值的动态规划题。
- 状态方程，jumps[x] 表示到每个位置最少需要跳跃几步。除了jumps[0] = 0， 其他初始值设为Interger.MAX_VALUE。
- 二重循环，外面i依次到每个位置。j循环 ( j < i )依依测试i前面位置到j的最小跳跃步数。
- 如果 A[j] + j > i (即j能够跳到i位置） 且 jumps[j] != Interger.MAX_VALUE （即f(j) 已经被检测过可以跳到），那么jumps[i] = Math.min(jumps[i], jumps[j] + 1) （比较之前得出的jumps[i]最小步数和现在正在进行的跳跃得出jumps[j] + 1的最小值）
- 最后一步所需跳跃次数就是 jumps[A.length – 1]的值。
参考代码
public class Solution {
/**
* @param A: A list of lists of integers
* @return: An integer
*/
public int jump(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
// the minimum jumps to i th position
int[] jumps = new int[A.length];
// init: needs MAX_VALUE to reach i positon except positon 0
jumps[0] = 0;
for (int i = 1; i < A.length; i++) {
jumps[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < i; j++) {
if (jumps[j] != Integer.MAX_VALUE && A[j] + j >= i) {
jumps[i] = Math.min(jumps[i], jumps[j] + 1);
}
}
}
return jumps[A.length - 1];
}
}