题解 | #打家劫舍(二)#

打家劫舍(二)

https://www.nowcoder.com/practice/a5c127769dd74a63ada7bff37d9c5815

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
    def sub_rob(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])

        dp = [0 for _ in range(n)]

        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        
        return dp[n-1]

    def rob(self, nums: List[int]) -> int:
        # write code here
        n = len(nums)

        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])
        if n == 3:
            return max(nums[0], nums[1], nums[2])
        
        nums_0 = nums[0: n-1]
        nums_1 = nums[1: n]

        res_0 = self.sub_rob(nums_0)
        res_1 = self.sub_rob(nums_1)

        return max(res_0, res_1)

全部评论

相关推荐

能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
05-22 09:23
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务