LeetCode-跳跃游戏

LeetCode-跳跃游戏,第1张

  • 动态规划思想
  1. 观察。

    我们设置dp数组,下标表示位置,值表示当前可跳最大步数。

  2. 确定状态方程。

    我们进行一步一步跳的 *** 作,假设我们要跳到第n个位置,那么dp[n-1]必须大于1,跳到位置n后,我们确定dp[n]的值。更新值来源于

    • dp[i-1]-1 前一步可跳步数减1
    • nums[i] 给出的可跳最大步数值

    我们只需找到这两个谁大就可以确定状态方程了。

    dp[i]=max{dp[i-1]-1,nums[i]}

  3. 确定边界条件

    由状态方程知i-1>=0,位置0时我们设置它最大步数为它本身,即dp[0]=nums[0]。

  4. 最终结果

    当dp[i]出现值为零的时候,但i却不等于numsSize-1,则不能到达,否则可以。

    注意:

    1. 当第0个位置为零的时候,无法使用状态方程,起始为零表面一开始就不能跳了。
    2. 当numsSize=1时,起始点即为终点。
bool canJump(int* nums, int numsSize){
    if(numsSize==1)
    return true;
    if(nums[0]==0)
    return false;
int dp[numsSize];
dp[0]=nums[0];
for(int i=1;i<numsSize;i++)
{
    dp[i]=fmax(--dp[i-1],nums[i]);
    if(dp[i]==0&&i!=numsSize-1)
    return false;
}
return true;
}

了解后,为了减少空间复杂度,将数组改为变量

bool canJump(int* nums, int numsSize){
    if(numsSize==1)
    return true;
    if(nums[0]==0)
    return false;
int a,b;
a=nums[0];
for(int i=1;i<numsSize;i++)
{
    b=fmax(--a,nums[i]);
    if(b==0&&i!=numsSize-1)
    return false;
    a=b;
}
return true;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/741968.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-28
下一篇 2022-04-28

发表评论

登录后才能评论

评论列表(0条)

保存