Lintcode -- Jump Game II / Greedy/ DP -【M】
http://www.lintcode.com/en/problem/jump-game-ii/
http://www.jiuzhang.com/solutions/jump-game-ii/
public class Solution {
/**
@param A: A list of lists of integers
@return: An integer
*/
public int jump(int[] A) {
// write your code here
int[] function = new int[A.length];
function[0] = 0;
for (int i = 1; i < A.length; i++) {
function[i] = Integer.MAX_VALUE;
}
for (int i = 1; i < A.length; i++) {
for (int j = 0; j < i; j++) {
if (function[j] != Integer.MAX_VALUE && j + A[j] >= i) {
function[i] = Math.min(function[i], function[j] + 1);
}
}
}
return function[A.length - 1];
}
}