IT 面试题库

LeetCode 198 打家劫舍:不能偷相邻两间房,求能偷到的最大金额。给出 DP 状态与转移。

中级编程题算法工程师Java后端工程师动态规划打家劫舍线性DP

题目

考察点:线性 DP 的『选/不选』取舍,以及滚动数组空间优化。

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 65 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

思路:对第 i 间房只有『偷』或『不偷』两种选择,取两者最大值。

要点(状态定义):

要点(实现与优化):

def rob(nums):
    prev2 = 0
    prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1
练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题