动态规划之打家劫舍

在leetcode上打家劫舍这个系列也是动态规划的题目,分支变形,难度逐渐加大。今天整理一下这个系列的题目,做个记录。

打家劫舍

打家劫舍

小偷在偷窃时,唯一的限制就是,不能同时偷相邻的两个房屋。

我们定义 dp[i] 为偷到第i家时能偷到的最大金额,那么偷到第i家时可能有两种情况:

  1. 第i-1家偷过,那么当前第i家就不能再偷了,此时 dp[i]=dp[i-1]
  2. 第i-1家没偷过,那么当前第i家是可以偷的,此时 dp[i]=dp[i-2]+nums[i]
  3. 这两种情况,取最大值便是偷到第i家时能够偷到的最大金额

因此,相应的状态转移公式为:

1
dp[i]= Math.max(dp[i-1], dp[i-2]+nums[i])

对于初始状态,dp[0]=nums[0]dp[1]=Math.max(nums[0], nums[1])

1
2
3
4
5
6
7
function rob(nums: number[]): number {
const dp = [nums[0], Math.max(nums[0], nums[1])];
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
};

打家劫舍II

2

这个题目相比较打家劫舍I而言,多了一个限制,数组为循环数组。也就是说,第一家和最后一家在物理上是挨着的,不能同时偷窃。

因此这个时候有两种情况需要考虑:

  1. 考虑第一个房子,但不考虑最后一个房子(抢第一个房子,不抢最后一个房子)
  • 抢第一个房子,不抢最后一个房子,相当于在 nums[0]...nums[n-2] 中进行打家劫舍
  1. 考虑最后一个房子,但不考虑第一个房子(抢最后一个房子,不抢第一个房子)
  • 抢最后一个房子,不抢第一个房子,相当于在 nums[1]...nums[n-1] 中进行打家劫舍
  1. 两种情况取最大值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function rob(nums: number[]): number {
if (nums.length == 1) return nums[0];
let max = -1;
const dp = new Array(nums.length).fill(0);

// 考虑第一家,不考虑最后一家
dp[0] = nums[0], dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length - 1; i++) {
dp[i] = Math.max(
dp[i - 2] + nums[i],
dp[i - 1]
);
}

max = dp[nums.length - 2];
// 考虑最后一家,不考虑第一家
dp[1] = nums[1], dp[2] = Math.max(nums[1], nums[2]);
for (let i = 3; i < nums.length; i++) {
dp[i] = Math.max(
dp[i - 2] + nums[i],
dp[i-1]
);
}
max = Math.max(max, dp[nums.length-1]);
return max;
}

打家劫舍III

3

这个题目是打家劫舍I和打家劫舍II的升级版,由原来的线性结构升级为二叉树结构。

和上面一样,对于每个节点(房屋),都有两种状态:偷和不偷。

我们用 f(n) 表示偷n节点的情况下,n节点的子树上能够偷到的最大值。
g(n)表示不偷n节点的情况下,n节点的子树上偷到的最大值。
l和r表示n的左右子树。

  • 当n被选偷时,n的左右孩子都不能被偷,故n被选中的情况下子树上被选中点的最大权值和为l和r不被选中的最大值和相加,即 f(n)=g(l)+g(r)
  • 当n不被偷时,n的左右孩子可以被偷,也可以不被偷。对于n的某个具体的孩子x,它对n的贡献值是x被选中和不被选中情况下权值和的较大值。故 g(n)=max(f(l),g(l))+max(f(r),g(r))

    注意这里,当n不被偷时,n的左右孩子即可能被偷,也可能不被偷。因为只要求说被偷的房子不连在一起即可,而不是必须间隔。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function rob(root: TreeNode | null): number {
const f = new Map();
const g = new Map();
// 深度优先遍历
const dfs = (node: TreeNode | null) => {
if (node == null) return;
// 先进行深度优先遍历,遍历完后才能根据子节点计算父节点的值
dfs(node.left);
dfs(node.right);

const gLeft = g.get(node.left) || 0;
const gRight = g.get(node.right) || 0;
const fLeft = f.get(node.left) || 0;
const fRight = f.get(node.right) || 0;

f.set(node, node.val + gLeft + gRight);
g.set(node,
Math.max(fLeft, gLeft) + Math.max(fRight, gRight)
);

}

dfs(root);
return Math.max(f.get(root) || 0, g.get(root) || 0)
};