首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。