lintCode (117) 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.

Have you met this question in a real interview? 

Yes

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

这题是哥白撕不得其姐的一道题。。。总是LTE， 事实上用了一个DP+贪婪，每次碰上贪婪哥就跪了，这个题目的贪婪在于，他认为越早发现能调到当前位置，那么步数就越少， 感觉很有道理的样子，但是实际是又说不出道理，哥只能妥协，为了过test case...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: /** * @param A: A list of lists of integers * @return: An integer */ int jump(vector<int> A) { // wirte your code here int n = A.size(); if (n==0 || A[0]==0) return 0; vector<int> tbl(n, INT_MAX); tbl[0]=0; for (int i=1 ; i<n ; i++){ for (int j=0; j<i; j++){ if (tbl[j]!=INT_MAX && j+A[j]>=i){ tbl[i]=tbl[j]+1; break; } } } return tbl[n-1]; } };