打家劫舍问题

状态表示:
- 集合: $f [i]$ 表示偷到第 $i$ 间的金钱数量
- 属性: 最大值
状态计算:列出状态转移方程
- $f [i] = ma x (f [i - 2] + n u m s [i], f [i - 1])$
  偷第 $i$ 间房, 可以从集合 $f [i - 2], f [i - 1]$ 转移过来, 如果偷, $f [i] = f [i - 2] + n u m s [i]$
  如果不偷, $f [i] = f [i - 1]$ 。对于这两种情况可以取一个最大值。

代码

没有经过空间优化


def rob(self, nums: List[int]) -> int:n = len(nums)f = [0] * (n+2)for i in range(n):f[i+2] = max(f[i+1], f[i] + nums[i])return f[-1]

空间优化


def rob(self, nums: List[int]) -> int:n = len(nums)f0, f1 = 0, 0 for i in range(n):f0 = max(f1, f0 + nums[i])f0, f1 = f1, f0return f1

2、打家劫舍II

题目描述

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下,今晚能够偷窃到的最高金额。

示例 1:

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋(金额 = 2), 然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

数据范围

$1 <= n u m s . l e n g t h <= 100$
$0 <= n u m s [i] <= 400$

思路

动态规划三部曲:

状态表示:
- 集合: $f [i]$ 表示偷到第 $i$ 间的金钱数量
- 属性: 最大值
状态计算:列出状态转移方程
- 和打家劫舍I不同的是,这次房屋是环绕形的,其实还是分割子问题
  - 因为关键在于环形:可以考虑将环拆开,然后分类讨论,如果偷 $n u m s [0]$ ,那么必定不偷 $n u m s [1], n u m s [n - 1]$ ,那么就是取 $n u m s [0] + ro b (n u m s [2 : n - 1])$
  - 如果不偷 $n u m s [0]$ , 那么就可以偷 $n u m s [1], n u m s [n - 1]$ ,那么就转换成了 $ro b (n u m s [1 :])$
    的问题。

代码


def rob(self, nums: List[int]) -> int:def rob1(nums: List[int]) -> int:n = len(nums)f0, f1 = 0, 0 for i in range(n):f0 = max(f1, f0 + nums[i])f0, f1 = f1, f0return f1return max(nums[0] + rob1(nums[2:-1]), rob1(nums[1:]))

3、打家劫舍III

题目描述

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 $roo t$ 。

除了 $roo t$ 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

给定二叉树的 $roo t$ 。返回在不触动警报的情况下 ,小偷能够盗取的最高金额。

在这里插入图片描述

示例 1:

输入：root = [3,2,3,null,3,null,1]
输出：7
解释：小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

在这里插入图片描述

示例 2:

输入：root = [3,4,5,1,3,null,1]
输出：9
解释：小偷一晚能够盗取的最高金额 4 + 5 = 9

数据范围

树的节点数在 $[1, 104]$ 范围内
$0 <= Node.val <= 10^4$

思路

动态规划三部曲:

状态表示:
- 集合: 采用 $f (o)$ 表示选择当前节点所能偷取的最大钱数, $g (o)$ 表示不选择当前节点所能偷取的最大钱数。
- 属性: 最大值
状态计算:列出状态转移方程
- 和打家劫舍I,II不同的是,这次针对的是树,其实相当于是在树上做 $D P$
  - 考虑 $f (o), g (o)$ ,怎么转移过来即可
    - $f (o) = g (l) + g (r) + o . v a l$
    - $g (o) = ma x (f (l), g (l)) + ma x (f (r), g (r))$

代码


def rob(self, root: Optional[TreeNode]) -> int:def dfs(root):if not root:return 0, 0fl, gl = dfs(root.left)fr, gr = dfs(root.right)f = root.val + gl + grg = max(fl, gl) + max(gr, fr)return f, greturn max(dfs(root))

4、打家劫舍IV

题目描述

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统,所以小偷不会窃取相邻的房屋。

小偷的窃取能力定义为他在窃取过程中能从单间房屋中窃取的最大金额。

给你一个整数数组 $n u m s$ 表示每间房屋存放的现金金额。形式上, 从左起第 $i$ 间房屋中放有 $n u m s [i]$ 美元。

另给你一个整数 $k$ ,表示窃贼将会窃取的最少房屋数。小偷总能窃取至少 $k$ 间房屋。

返回小偷的最小窃取能力。

示例 1:

输入：nums = [2,3,5,9], k = 2
输出：5
解释：小偷窃取至少 2 间房屋,共有 3 种方式：

窃取下标 0 和 2 处的房屋,窃取能力为 max(nums[0], nums[2]) = 5 。
窃取下标 0 和 3 处的房屋,窃取能力为 max(nums[0], nums[3]) = 9 。
窃取下标 1 和 3 处的房屋,窃取能力为 max(nums[1], nums[3]) = 9 。
因此,返回 min(5, 9, 9) = 5 。

示例 2:

输入：nums = [2,7,9,3,1], k = 2
输出：2
解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。

数据范围

$1 <= n u m s . l e n g t h <= 105$
$1 <= n u m s [i] <= 109$
$1 <= k <= (n u m s . l e n g t h + 1) /2$

思路

这个是套了一层二分答案壳子的打家劫舍I
- 首先最小化最大窃取能力可以直接联想到二分答案
- 如果小偷的窃取能力越强,越有可能偷够k间房屋,所以答案具有单调性

代码


def minCapability(self, nums: List[int], k: int) -> int:n = len(nums)def check(mid):f0, f1 = 0, 0for x in nums:f0 = max(f1, f0 + (mid >= x))f1, f0 = f0, f1return f1 >= kl, r = min(nums), max(nums)while l < r:mid = (l + r) // 2if check(mid):r = midelse:l = mid + 1return l