198打家劫舍

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def rob(self, nums: List[int]) -> int:
        # 一道经典的 动态规划题。
        # d[j] 定义为 到 j 号房间为止，能够偷窃到的最高金额;
        # d[j] 有两种情况：
        # 情况一： 取到j号房间的钱了，那之前抢劫的房间就只能考虑到 j-2 号房间，因为不能连续房间抢劫。
        # 情况二： 没有取到j号房间的钱，那之前抢劫的房间能考虑到 j-1 号房间。
        # d[j] = max(情况一,情况二) = max(d[j-2]+j号房间的钱,d[j-1])
        # 遍历顺序 从小到大即可
        # 初始化 d[0] = 0号的钱。 d[1] = max(1号，0号)
        d = [0 for _ in range(len(nums))]
        if len(nums)==1: return nums[0]
        elif len(nums)==2: return max(nums[0],nums[1])
        d[0],d[1] = nums[0],max(nums[0],nums[1])
        for i in range(2,len(nums)):
            d[i] = max(d[i-2]+nums[i],d[i-1])
            print(d)
        return d[len(nums)-1]