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.

分析：

state: f[i] 跳到第i步所需要的最小步数

function: f[i] = min(f[j], j from 0 to i - 1 && A[j] >= i - j)

initialization: f[0] = 0

answer: f[n - 1]

这些题目用DP做，复杂度在O(n^2)，只是优于枚举法的指数级复杂度，而不如贪心法的线性复杂度！

解法：

class Solution {
public:
    /**
     * @param A: A list of lists of integers
     * @return: An integer
     */
    int jump(vector<int> A) {
        // wirte your code here
        if (A.size() == 0 ) {
            return 0;
        }

        if (A[0] == 0 && A.size() > 1) {
            return -1;
        }

        int n = A.size();
        vector<int> res(n, 0);

        for (int i = 1; i < n; i++) {
            int prev = INT_MAX;
            for (int j = i - 1; j >= 0; j--) {
                if (A[j] >= i - j) {
                    prev = min(prev, res[j]);
                }
            }
            res[i] = prev + 1;
        }

        return res[n - 1];
    }
};