力扣-198.打家劫舍

Node_Su

已于 2022-04-25 13:27:20 修改

阅读量545

点赞数

分类专栏：学习笔记文章标签： python

于 2022-04-23 13:51:56 首次发布

本文链接：https://blog.csdn.net/Node_Su/article/details/124363035

版权

学习笔记专栏收录该内容

48 篇文章

订阅专栏

本文介绍了两种使用动态规划的方法来解决打劫问题，即在不触动相邻房屋的情况下，从一串房屋中最大化抢劫金额。解法一是考虑是否抢劫当前房屋，而解法二是根据前两家的情况决定当前家是否抢劫。这两种方法都通过比较不抢劫和抢劫当前房屋的收益来确定最佳策略。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

解法一：

dp[i]表示打劫到当前第 i 家的最大金额

首先，前3家特殊处理

然后，是否打劫当前家应考虑打劫 i-2 家和 i-3 是否能达到最大收益，因为不能打劫邻居 i-1

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)

        dp = [0] * n # 初始钱包为0
        dp[0] = nums[0]
        if n == 1:
            return nums[0]
        if n == 2:
            dp[1] = max(nums[0], nums[1])
            return dp[1]
        if n >= 3:
            dp[1] = max(nums[0], nums[1])
            dp[2] = max(nums[0] + nums[2], nums[1])
            for i in range(3, n):
                dp[i] = max(dp[i - 2] + nums[i], dp[i - 3] + nums[i])
            res = -1
            for i in range(n):
                res = max(dp[i], res)
            return res


if __name__ == '__main__':
    nums = [1, 2, 1, 1]
    Sol = Solution()
    res = Solution.rob(Sol, nums)
    print(res)

解法二：

考虑当前家偷不偷

如果偷，则是 i-2 家的金额+当前家的金额

如果不偷，则是偷前 i-1 家的金额

比较两种情况的大小

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)

        dp = [0] * n
        dp[0] = nums[0]
        if n == 1:
            return nums[0]

        dp[1] = max(nums[1], nums[0])
        for i in range(2, len(nums)):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])  # 不偷，偷
        return dp[len(dp) - 1]


if __name__ == '__main__':
    nums = [1]
    Sol = Solution()
    res = Solution.rob(Sol, nums)
    print(res)