第一种比较容易的想法，可以建立一个标志数组，每一位的1或者0代表是否能到达这一位，在遍历该数组的同时根据数组值更新标志数组的值。本来是没通过的，有一个改进处在于遍历到一个能够到达的节点后，首先判断从该节点出发是否能到达最后一位，如果可以就直接返回，不行的话，就老实更新数组。贴代码
1 class Solution { 2 public: 3 bool canJump(vector<int>& nums) 4 { 5 vector<int> flag(nums.size(),0); 6 flag[0] = 1; 7 for(int i = 0 ; i < nums.size() ; i++) 8 { 9 if(flag[i]) 10 { 11 if(nums[i]+i>=nums.size()-1) 12 return true; 13 for(int j = 1 ; j <= nums[i] && i+j<nums.size() ; j++) 14 { 15 flag[i+j] = 1; 16 } 17 } 18 } 19 return flag[nums.size()-1]; 20 } 21 };
所谓的贪心算法，维护一个表示当前能够到达的最远位置的变量，为max_pos，所有小于等于该变量的位置都能够达到。在遍历数组的过程中，如果当前位置的索引小于等于max_pos，代表该位置可以达到，并且计算从该位置出发能够到达的最远位置，与max_pos比较，若更大，则将该值赋给max_pos。在遍历过程中，若max_size大于最远索引，则直接返回。仔细想了下和自己方法的区别，就一个不同，用一个变量代替了我整个数组，所以内存的消耗和赋值的开销都小很多。贴代码
1 class Solution { 2 public: 3 bool canJump(vector<int>& nums) 4 { 5 int max_pos = 0; 6 int n = nums.size(); 7 for(int i = 0 ; i < nums.size() ; i++) 8 { 9 if(i<=max_pos) 10 { 11 max_pos = max(max_pos,i+nums[i]); 12 } 13 if(max_pos>=n-1) 14 return true; 15 } 16 return false; 17 } 18 };