Problem: 55. 跳跃游戏
题目描述
思路
我们将问题稍做转换每次求取当前位置可以走到的最远位置，在此基础上我们将最终判断是否能走出整个nums；同时我们要判断中途会不会遇到某个位置是0使得不能继续走下去
复杂度
时间复杂度:
O ( n ) O(n) O(n)；其中 n n n为数组nums的大小
空间复杂度:文章来源：https://www.toymoban.com/news/detail-832839.html
O ( 1 ) O(1) O(1)；文章来源地址https://www.toymoban.com/news/detail-832839.html
Code
class Solution {
public:
/**
* Dynamic programming
*
* @param nums Given array
* @return bool
*/
bool canJump(vector<int>& nums) {
int n = nums.size();
int farthest = 0;
for (int i = 0; i < n - 1; ++i) {
farthest = max(farthest, i + nums[i]);
//Meet to 0
if (farthest <= i) {
return false;
}
}
return farthest >= n - 1;
}
};
到了这里，关于力扣55. 跳跃游戏（动态规划）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
