Sunday, December 23, 2012

[LeetCode] Jump Game 解题报告

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.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
» Solve this problem

[解题报告]

jump[i] = max(jump[i-1], A[i-1]) -1, i!=0
= 0 , i==0

[Code]
1:  bool canJump(int A[], int n) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      int* jump = new int[n];
5:      jump[0] = 0;
6:      for(int i=1; i < n; i++)
7:      {
8:        jump[i] = max(jump[i-1], A[i-1]) -1;
9:        if(jump[i] <0)
10:          return false;;
11:      }
12:      return jump[n-1] >=0;
13:    }

Update, 3/14/2013
Just one round DP. No need an array to track the status. Refactor the code.
1:       bool canJump(int A[], int n) {
2:            int maxCover = 0;
3:            for(int start =0; start<= maxCover && start<n; start++)
4:            {
5:                 if(A[start]+start > maxCover)
6:                      maxCover = A[start]+start;
7:                 if(maxCover >= n-1) return true;
8:            }
9:            return false;
10:       }