思路
解法一 贪心优化之后的dp
时间复杂度
$O(n)$
空间复杂度 $O(n)$
int jump(int* nums, int numsSize) {
int dp[numsSize];
memset(dp, 0, sizeof(dp));
int last = 0;
for(int i = 1; i < numsSize; i++){
while(last <= i && last + nums[last] < i) last++;
dp[i] = dp[last] + 1;
}
return dp[numsSize - 1];
}
解法二 双指针+贪心
时间复杂度
$O(n)$
空间复杂度
$O(1)$
int jump(int* nums, int numsSize) {
int res = 0;
int dis = 0;
int next = 0;
int cur = 0;
while(dis < numsSize - 1){
while(cur <= dis){
if(cur + nums[cur] > next){
next = cur + nums[cur];
}
cur++;
}
res ++;
dis = next;
}
return res;
}