关于#算法#的问题：这个道题的switch为啥只选taken[0]哇

Question

https://leetcode.cn/problems/8Zf90G/solutions/1398937/hou-zhui-biao-da-shi-by-leetcode-solutio-39j5/
这个道题的switch为啥只选taken[0]哇？[]

Answer 1

引自免费微信小程序：皆我百晓生

这道题是LeetCode上的题目“House Robber III”，目标是解决一个动态规划问题，给定一个由非负整数构成的二维数组 nums，表示若干栋房子，每栋房子内有若干房间，每个房间都有不同的金额。每栋房子之间可以通过门相连，但只能通过门从一个房间进入下一个房间，并且一旦离开一栋房子就不能再返回。此外，每次进入一栋房子时，可以选择不抢劫它，但一旦决定抢劫某栋房子，则必须抢劫完所有房间。任务是计算出最大可以盗取的金额。

提供的解决方案中，有一个名为 dp 的动态规划数组，用于存储到达某个房间的最大盗窃金额。还有一个布尔数组 taken，记录了是否已经抢劫过某个房子。当遍历到某个房间时，会根据当前房间的状态（是否已被抢劫）来选择最优解。

具体来说，对于每个房间 (row, col)，我们有两种可能的情况：

1. 如果之前没有抢劫过这一栋房子（即 taken[row] == false），那么我们可以选择抢劫或者不抢劫这栋房子。

   • 如果抢劫，我们将得到 nums[row][col] + dp[row + 1]（抢劫当前房间并继续前进）的收益，因为抢劫后不能再回到这栋房子，所以只能前进。
   • 如果不抢劫，我们就完全跳过这栋房子，得到的是 dp[row + 1]（仅考虑前进的情况）的收益。

2. 如果之前已经抢劫过这一栋房子（即 taken[row] == true），那么我们就不能再次进入这栋房子，所以我们只能从上一栋房子的选择中获取最大收益，即 dp[row - 1]。

在计算过程中，我们需要更新 dp[col] 的值为上述两种情况中的较大者。然后根据新得到的 dp[col] 值更新 taken[col]，以备后续房间的决策参考。这里 taken[0] 只是一个初始化状态，表示第一栋房子是否被抢劫。实际运行过程中，会根据状态转移方程更新 taken 数组。

下面是完整的Python代码实现：

def rob(nums):
    if not nums:
        return 0
    
    n = len(nums)
    dp = [0] * n
    taken = [False] * n

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

    for i in range(2, n):
        dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
        
        # 更新taken数组，根据dp[i]的变化决定是否抢劫第i栋房子
        taken[i] = dp[i] > dp[i - 1]

    return max(dp)

# 测试数据
nums = [1, 2, 3, 1]
print(rob(nums))  # 输出: 4

这段代码首先初始化了 dp 和 taken 数组，然后按照状态转移方程计算每个房间的最大盗窃金额。最终返回整个数组 dp 中的最大值作为答案。