[Leetcode] Jump Game I and II

Problem 

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,
1. If you are able to reach the last index.
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

2. The minimum number of jumps to reach the last index.
Input A = [2,3,1,1,4], the minimum number of jumps to reach the last index is 2, i.e. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Algorithm

1. O(n^2)
Let dp[i] indicates whether we can reach A[i]. The recurrence reads

         dp[i] =  OR(dp[j] == true AND A[j] >= (i-j)),     0<= j < i

In the second problem, let dp[i] = the minimum number of steps to reach A[i]. Then,
                                        dp[i] = min(dp[j]+1), where A[j] >= (i-j) for all j<i

2. O(n) 
Maintain a window [l, r], which can be reached in nSteps jumps. Iterate each indices in this range, compute the maximum index can be reached in one more step. Then, this new window can be reached in nSteps +1 jumps. If after one iteration, the window cannot be moved any farther and we  still not reach the end of the array. We say the end of the array is not reachable.

Code