首页 > 代码库 > 055. Jump Game

055. Jump Game

方法一:递归,超时

 1 class Solution { 2 public: 3     bool canJump(vector<int>& nums) { 4         if (nums.size() < 2) return true; 5         else { 6             for (int i = 1; i <= *nums.begin(); ++i) { 7                 vector<int> vec(nums.begin() + i, nums.end()); 8                 if (canJump(vec)) return true; 9             }10             return false;11         }12     }13 };

 

方法二:动态规划

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

 

055. Jump Game