美文网首页LeetCode动态规划
55.跳跃游戏错在哪里

55.跳跃游戏错在哪里

作者: cptn3m0 | 来源:发表于2019-03-23 08:11 被阅读0次

    背景介绍

    这是再次复习这道题目的遇到的问题

    DP 状态

    dp[i] 表示跳到i,包括i之后, 还剩余的跳跃步数.
    dp[0] 表示起点, dp[0]=nums[0]

    排除法

    1. dp 初始化过程没有问题
    2. 应该是dp 推导过程出现了问题

    举个例子

    输入

    [3,2,1,0,4]
    

    打印出来 dp数组

    [3, 2, 1, 0, -1]
    

    问题所在, 就是如果判断dp[i-1]会有遗漏, 导致最后一个问题出错.


    看看代码

    class Solution(object):
        def canJump(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            # dp 算法求解
            # dp[i] 表示到达 i 的时候, 剩余的长度
            
            n = len(nums)
            dp = [0]*n
            ## 初始值
            dp[0] = nums[0]
            for i in range(1,n):
                if dp[i-1] == 0:
                    return False
                dp[i] = max(dp[i-1],nums[i-1])-1
            
            return True
    

    相关文章

      网友评论

        本文标题:55.跳跃游戏错在哪里

        本文链接:https://www.haomeiwen.com/subject/mcjjvqtx.html