DP and boundary thought of this problem


  • 0
    E

    i see no body use dp in this problem, so just provide another kind of method.

    int jump(vector<int>& nums) {
      int n = nums.size();
      if (n == 0) return 0; 
      int *steps = new int[n];
      for (int i = 1; i < n; i++) steps[i] = n + 1;
      steps[0] = 0;
      for (int i = 0; i < n; i++) {
        if (steps[i] < 0) continue;
        for (int j = 1; j <= nums[i] && i + j < n; j++) {
          if (i + j < n - 1 && nums[i] - j >= nums[i + j]) steps[i + j] = -1;
          else if (steps[i + j] > steps[i] + 1) steps[i + j] = steps[i] + 1;
        }
      }
      return steps[n - 1];
    }

  • 0
    D

    how about the empty array ? I remember leetcode has empty array test case.


  • 0
    E

    yeah u are right, it's wrong in empty case. I guess leetcode has no empty array test, but it's necessary. I edit it to handle that.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.