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.)
解題思路：
最值問題，第一想到的就是動態規劃。用d[i]記錄從0到i最小的步數，則d[i]=min(d[k]+1)，其中k是所有能夠到達i的下標。最開始，我用一個vector數組記錄所有能夠到達自身的下標，代碼如下：
class Solution {
public:
int jump(vector& nums) {
int len = nums.size();
if(len<2){
return 0;
}
int d[len];
d[0] = 0;
vector pre[len];
for(int i=1; i<=nums[0] && i時間復雜度為O(n*n)，空間復雜度為O(n*n)。超時錯誤。
後經過改進，不需要記錄前驅節點，代碼如下，空間復雜度變為O(n)，但時間復雜度仍為O(n*n)，產生超時錯誤。
class Solution {
public:
int jump(vector& nums) {
int len = nums.size();
if(len<2){
return 0;
}
int d[len];
for(int i=1; i水中的<。)#)))≦給我們一個非常好的解法：http://fisherlei.blogspot.com/2012/12/leetcode-jump-ii.html，采用貪心算法，記錄第k步最多能夠走，且對第k+1步有影響的范圍[Left, Right]，每走一步，left變成right+1，right變成[left, right]區間內走一步最遠的下標。這裡與上述方法的根本區別就是left=right+1，而非left=left+1，這樣能夠減少很多計算。因為[left+1,
right]已經在[left, right]時已經計算過了。
class Solution {
public:
int jump(vector& nums) {
int len = nums.size();
int left = 0;
int right = 0;
int count = 0;
while(right=len - 1){
break;
}
}
left = right + 1;
right=mostRight;
if(right
