https://leetcode.cn/problems/8Zf90G/solutions/1398937/hou-zhui-biao-da-shi-by-leetcode-solutio-39j5/
这个道题的switch为啥只选taken[0]哇?[]
![](https://profile-avatar.csdnimg.cn/default.jpg!4)
关于#算法#的问题:这个道题的switch为啥只选taken[0]哇
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
6条回答 默认 最新
关注
引自免费微信小程序:皆我百晓生
这道题是LeetCode上的题目“House Robber III”,目标是解决一个动态规划问题,给定一个由非负整数构成的二维数组
nums
,表示若干栋房子,每栋房子内有若干房间,每个房间都有不同的金额。每栋房子之间可以通过门相连,但只能通过门从一个房间进入下一个房间,并且一旦离开一栋房子就不能再返回。此外,每次进入一栋房子时,可以选择不抢劫它,但一旦决定抢劫某栋房子,则必须抢劫完所有房间。任务是计算出最大可以盗取的金额。提供的解决方案中,有一个名为
dp
的动态规划数组,用于存储到达某个房间的最大盗窃金额。还有一个布尔数组taken
,记录了是否已经抢劫过某个房子。当遍历到某个房间时,会根据当前房间的状态(是否已被抢劫)来选择最优解。具体来说,对于每个房间 (row, col),我们有两种可能的情况:
-
如果之前没有抢劫过这一栋房子(即
taken[row] == false
),那么我们可以选择抢劫或者不抢劫这栋房子。- 如果抢劫,我们将得到
nums[row][col] + dp[row + 1]
(抢劫当前房间并继续前进)的收益,因为抢劫后不能再回到这栋房子,所以只能前进。 - 如果不抢劫,我们就完全跳过这栋房子,得到的是
dp[row + 1]
(仅考虑前进的情况)的收益。
- 如果抢劫,我们将得到
-
如果之前已经抢劫过这一栋房子(即
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
中的最大值作为答案。解决 无用评论 打赏 举报 编辑记录-
悬赏问题
- ¥15 电子档案元素采集(tiff及PDF扫描图片)
- ¥15 flink-sql-connector-rabbitmq使用
- ¥15 zynq7015,PCIE读写延时偏大
- ¥15 使用spss做psm(倾向性评分匹配)遇到问题
- ¥20 vue+UEditor附件上传问题
- ¥15 想做个WPS的自动化代码,不知道能做的起不。
- ¥15 uniApp,生成安卓安卓包后,黑暗主题中间内容不生效,底部导航正常
- ¥15 斯坦福自动漂移非线性模型反解
- ¥15 学习Python如何找兼职
- ¥15 python结合Matlab仿真忆阻器