Jump Game II

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

http://www.lintcode.com/en/problem/jump-game-ii/

Notes

跟Jump Game一样可以用DP或者贪心法来接。

• f[i]表示从0到i的minimum jumps

• 状态变化方程 f[i] = i之前第一个能到达i的f[j]+1 。要求第一个是为了保证最少的jumps

  • 怎么把这句话转化成程序语言？

    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) return INT_MAX;
      vector<int> s(n, INT_MAX);
      s[0] = 0;
      for(int i=1; i<n; i++) {
          for(int j=0; j<i; j++) {
              if(A[j]+j>=i && s[j] != INT_MAX) { 
                  s[i] = s[j]+1;
                  break;
              }
          }
      }
      return s[n-1];
    }
    };
    

    A[j]+j>=i就表示能到达i的j。

    如果确定是有解的，则无需比较s[j] != INT_MAX （这是为了保证j可以从0可达）

贪心法：

思想是总是从跳到最远的地方开始下一跳！

转成程序语言就是当i>farthest时，同时也更新farthest 那用什么更新farthest嘞？

int jump(vector<int> A) {
        if(A.empty()) return 0;
        int n = A.size();
        int reachable = 0;//decide the farthest position reachable
        int current_reachable = 0;//decides jump or not
        int cnt = 0;
        for(int i=0; i<n; i++) {
            if(reachable < i) return INT_MAX; //NOT reachable from 0
            if(current_reachable < i) {//NOT reachable from last jump
                cnt++;
                current_reachable = reachable;
            }
            reachable = max(reachable, A[i]+i);
        }
        return cnt;
    }

Complexity

贪心法是$$O(n)$$, DP是$$O(n^2)$$.