符合动态规划的条件:
- 每个状态与前一个状态有关——设到i的最少步数为f(i),则f(i) = f(i的上一个点) + 1
- 初始状态是已知的——刚开始几个点的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; } };