跳跃游戏II

符合动态规划的条件：

1. 每个状态与前一个状态有关——设到i的最少步数为f(i)，则f(i) = f(i的上一个点) + 1
2. 初始状态是已知的——刚开始几个点的f与第一个点有关

然后就是实现问题了，两个循环，外循环是遍历每个点，内循环是遍历当前点的“势力范围”。

class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @return int整型
     */
    int jump(int *A, int n) {
        // write code here
        // 动态规划：设到i的最少步数为f(i)，则f(i) = f(i的上一个点) + 1
        // dp数组保存到第i个点最少的步数
        if (n <= 1) return 0;
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            int maxIdx = min(A[i] + i, n - 1);  // 从i走能到的最大位置
            for (int j = i + 1; j <= maxIdx; ++j) {
                if (dp[j] == 0) dp[j] = dp[i] + 1; // 位置没有被走过，保存最小步数
            }
            if (dp[n - 1] != 0) return dp[n - 1];
        }
        return -1;
    }
};