C++刷LeetCode（55. 跳跃游戏）【动态规划】【贪心思想】

糖逗

题目描述：

1. 
   
2. 给定一个非负整数数组，你最初位于数组的第一个位置。
   
3. 
   
4. 数组中的每个元素代表你在该位置可以跳跃的最大长度。
   
5. 
   
6. 判断你是否能够到达最后一个位置。
   
7. 
   
8. 示例 1:
   
9. 
   
10. 输入: [2,3,1,1,4]
    
11. 输出: true
    
12. 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
    
13. 示例 2:
    
14. 
    
15. 输入: [3,2,1,0,4]
    
16. 输出: false
    
17. 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

复制代码

1. class Solution {
   
2. public:
   
3.     bool canJump(vector<int>& nums) {
   
4.         int len = nums.size();
   
5.         if(len == 1)return true;
   
6.         if(nums[0] == 0)return false;
   
7.         vector<bool> dp(len, false);
   
8.         dp[0] = true;
   
9.         for(int j = 1; j < len; j++){
   
10.             for(int i = j-1; i >= 0; i--){
    
11.                 if(nums[i] == 0)continue;
    
12.                 if(nums[i] + i >= j && dp[i] == true){
    
13.                     dp[j] = true;
    
14.                     break;
    
15.                 }
    
16.             }
    
17.         }
    
18.         return dp[len-1];
    
19.     }
    
20. };

复制代码

糖逗

勉强通过