55. 跳跃游戏
题目描述
思路分析
f
[
i
]
f[i]
f[i]:能否跳到位置i，能为
t
r
u
e
true
true，不能为
f
a
l
s
e
false
false
朴素方程：
f
[
i
]
f[i]
f[i]=
0
+
n
u
m
s
[
0
]
>
=
i
0+nums[0]>=i
0+nums[0]>=i&&
f
[
0
]
f[0]
f[0] ||
1
+
n
u
m
s
[
1
]
>
=
i
1+nums[1]>=i
1+nums[1]>=i&&
f
[
1
]
f[1]
f[1] ||…||
i
−
1
+
n
u
m
s
[
i
−
1
]
>
=
0
i-1+nums[i-1]>=0
i−1+nums[i−1]>=0&&
f
[
i
−
1
]
f[i-1]
f[i−1]
-> 思考：如何优化？
首先思考得出结论：如果能跳到i，则必然能跳到
i
i
i之前的任何位置。
有了这个结论，就可以做了。假设我们走到了
i
i
i，只需要判断
[
0
,
i
−
1
]
[0,i-1]
[0,i−1]上最大的
n
u
m
s
[
k
]
+
k
nums[k]+k
nums[k]+k是否大于或等于i即可。
代码实现
class Solution {
public:
bool canJump(vector<int>& nums) {
for(int i=0,j=0;i<nums.size();i++){
if(i>j) return false;
j=max(j,i+nums[i]);
}
return true;
}
};