算法练习（9）—— Jump Game II
习题
本题取自 leetcode 中的 Greedy 栏目中的第45题：
Jump Game II
题目如下：
Description
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.
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.)
Note
You can assume that you can always reach the last index.
思路与代码
- 首先理解题意。以题目中给的例子来看，一开始index在0，最大能跳2格。那么就是第一步可以跳到A[1]也可以跳到A[2]，就这样以此类推，最后要跳到最后一格（题目中已经假定最后一格一定可以到达），求跳的最少次数。
- 看起来是一个很简单的问题。因为最近一直在做动态规划的习题，这题一下子就去想了状态转移方程，让我们考虑几种情况。
- 假设dp[i]为在
index = i时最少的步数，那么，dp[i]就可以取决于是否走dp[i -1]，并且dp[i -1]是否能到达dp[i]。 - 像上面那样写显然过于复杂，因为从后往前太过繁琐，因为大部分的地方都可以走相邻的步，所以我们考虑从头往尾走。尽量走最多步数，不行再回退。这样想想，仿佛用贪心更加合适，也更加快
具体代码如下：
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();int step = 0, start = 0, end = 0;while (end < n - 1) {step++; int maxend = end + 1;for (int i = start; i <= end; i++) {if (i + nums[i] >= n - 1)return step;maxend = max(maxend, i + nums[i]);}start = end + 1;end = maxend;}return step;}
};