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.

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

tag: greedy

虽然tag中提示是greedy，但我却以为算法是动态规划。

构建一个动态规划数组dp，dp[i]表示跳到i处所需要的最少步骤。需要注意数组长度为1的情况。

class Solution {
public:
    int jump(int A[], int n) {
        int dp[n];
        int right = 0;
        int lastRight = 1;
        dp[0] = 0;
        for(int i = 0; i < n; i++){
            right = max(right, A[i] + i);
            if(right >= n - 1) {
                if(i == n - 1) return dp[i];
                else return dp[i] + 1;
            }
            while(lastRight <= right){
                dp[lastRight] = dp[i] + 1;
                lastRight++;
            }
        }
    }
};