Fork me on GitHub

数据结构与算法-7-动态规划-打家劫舍系列

一、打家劫舍系列

解决动态规划问题就是找「状态」和「选择」,仅此而已。

假想你就是这个专业强盗,从左到右走过这一排房子,在每间房子前都有两种选择:抢或者不抢。

「状态」和「选择」:你面前房子的索引就是状态,抢和不抢就是选择。

198.打家劫舍

链接:https://leetcode-cn.com/problems/house-robber/

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

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

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

题解一(动态规划):

1、定义数组元素的含义
    数组nums:各个房间的现金
    数组flags:记录各个房间有没有被偷,若flag = 0 则没偷, flag = 1 则偷了。
    数组dp:dp[i]代表前i个房屋偷到的最大现金数
2、递推方程式
    1)只考虑前两个房间时,谁大选谁
    2)考虑第三个房间

        如果偷第三个房间,则意味着第二个房间不偷,也就是第三个房间值 + 第一个房间的宝藏数量;
        如果不偷第三个房间,则宝藏数量等于前两个房间宝藏数量;

    dp[i]=max(nums[i]+dp[i-2],dp[i-1])
3、初始值
第一个房间:

    Condistion 1 :dp[0] = nums[0] ; flags[0] = 1;
    Condistion 2 :dp[0] = 0; flags[0] = 0;

第二个房间:

    Condistion 1 :when flags[1] = 1; dp[1] = nums[1];

    Condistion 2 :when flags[1] = 0; dp[1] = dp[0];

    选 Condistion 1 还是 Condistion 2呢?比较 两种情况下dp[1]的大小推广到前i个房间: (i>=2)

    when flags[i] = 1, dp[i] = nums[i] + dp[i-2]
    when flags[i] = 0; dp[i] = dp[i-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def rob(self, nums: List[int]) -> int:
lens=len(nums)
if lens==0:
return 0

# flag=lens*[0]
dp=lens*[0]

dp[0]=nums[0]
if lens<2:
return dp[0]
dp[1]=max(nums[0],nums[1])
for i in range(2,lens):
dp[i]=max(nums[i]+dp[i-2],dp[i-1])

return dp[lens-1]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums)==0:
return 0
if len(nums)<=2:
return max(nums)
dp=[0]*2
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
for i in range(2,len(nums)):
dp[i%2]=max(dp[(i-1)%2],dp[(i-2)%2]+nums[i])
return max(dp) # return dp[(len(nums)-1)%2]

题解二(自顶向下):

超时
1
2
3
4
5
6
7
8
9
class Solution:
def rob(self, nums: List[int]) -> int:
return self.dp(nums,0)
def dp(self,nums,start):
if start >= len(nums):
return 0
# 不抢,去下家;抢,去下下家
res=max(self.dp(nums,start+1),nums[start]+self.dp(nums,start+2))
return res

使用备忘录进行优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def rob(self, nums: List[int]) -> int:
# 初始化备忘录
self.memo={}
for i in range(len(nums)):
self.memo[i]=-1

return self.dp(nums,0)
def dp(self,nums,start):
if start >= len(nums):
return 0
# 避免重复计算
if self.memo[start] != -1:
return self.memo[start]
# 不抢,去下家;抢,去下下家
res=max(self.dp(nums,start+1),nums[start]+self.dp(nums,start+2))

# 记入备忘录
self.memo[start]=res
return res

题解二(自顶向下的动态规划):

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def rob(self, nums: List[int]) -> int:
n=len(nums)
if not nums:
return 0
if n<2:
return nums[0]
dp=[0]*(n)
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
for i in range(2,n):
dp[i]=max(dp[i-1],nums[i]+dp[i-2])
return dp[n-1]
1
2
3
4
5
6
7
8
9
10
11
int rob(int[] nums) {
int n = nums.length;
// dp[i] = x 表示:
// 从第 i 间房子开始抢劫,最多能抢到的钱为 x
// base case: dp[n] = 0
int[] dp = new int[n + 2];
for (int i = n - 1; i >= 0; i--) {
dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
}
return dp[0];
}

空间复杂度:

1
2
3
4
5
6
7
8
9
10
11
12
13
int rob(int[] nums) {
int n = nums.length;
// 记录 dp[i+1] 和 dp[i+2]
int dp_i_1 = 0, dp_i_2 = 0;
// 记录 dp[i]
int dp_i = 0;
for (int i = n - 1; i >= 0; i--) {
dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i;
}

213. 打家劫舍 II

链接:https://leetcode-cn.com/problems/house-robber-ii/

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

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

示例 1:

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

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

题解一(动态规划):

思路:
    在 [0:n-1] 中找到最大值
    在 [1:n] 中找到最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def rob(self, nums: List[int]) -> int:
def helper(nums):
if not nums:
return 0
n=len(nums)
if n==1:
return nums[0]
dp=[0]*n
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
for i in range(2,n):
dp[i]=max(dp[i-2]+nums[i],dp[i-1])
return dp[-1]
if not nums:
return 0
if len(nums)==1:
return nums[0]
return max(helper(nums[1:]),helper(nums[:len(nums)-1]))

首尾房间不能同时被抢,那么只可能有三种不同情况:
    要么都不被抢;
    要么第一间房子被抢最后一间不抢;
    要么最后一间房子被抢第一间不抢。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(robRange(nums, 0, n - 2),
robRange(nums, 1, n - 1));
}

// 仅计算闭区间 [start,end] 的最优结果
int robRange(int[] nums, int start, int end) {
int n = nums.length;
int dp_i_1 = 0, dp_i_2 = 0;
int dp_i = 0;
for (int i = end; i >= start; i--) {
dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i;
}

337. 打家劫舍 III

链接:https://leetcode-cn.com/problems/house-robber-iii/

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int rob(TreeNode root) {
if (root == null) return 0;

int money = root.val;
if (root.left != null) {
money += (rob(root.left.left) + rob(root.left.right));
}

if (root.right != null) {
money += (rob(root.right.left) + rob(root.right.right));
}

return Math.max(money, rob(root.left) + rob(root.right));
}

memo记忆化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int rob(TreeNode root) {
HashMap<TreeNode, Integer> memo = new HashMap<>();
return robInternal(root, memo);
}

public int robInternal(TreeNode root, HashMap<TreeNode, Integer> memo) {
if (root == null) return 0;
if (memo.containsKey(root)) return memo.get(root);
int money = root.val;

if (root.left != null) {
money += (robInternal(root.left.left, memo) + robInternal(root.left.right, memo));
}
if (root.right != null) {
money += (robInternal(root.right.left, memo) + robInternal(root.right.right, memo));
}
int result = Math.max(money, robInternal(root.left, memo) + robInternal(root.right, memo));
memo.put(root, result);
return result;
}

每个节点可选择偷或者不偷两种状态,根据题目意思,相连节点不能一起偷

当前节点选择偷时,那么两个孩子节点就不能选择偷了
当前节点选择不偷时,两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)
我们使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷,1 代表偷
任何一个节点能偷到的最大钱的状态可以定义为

当前节点选择不偷:当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
当前节点选择偷:当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
表示为公式如下

root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + Math.max(rob(root.right)[0], rob(root.right)[1])

root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int rob(TreeNode root) {
int[] result = robInternal(root);
return Math.max(result[0], result[1]);
}

public int[] robInternal(TreeNode root) {
if (root == null) return new int[2];
int[] result = new int[2];

int[] left = robInternal(root.left);
int[] right = robInternal(root.right);

result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
result[1] = left[0] + right[0] + root.val;

return result;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Map<TreeNode, Integer> memo = new HashMap<>();
public int rob(TreeNode root) {
if (root == null) return 0;
// 利用备忘录消除重叠子问题
if (memo.containsKey(root))
return memo.get(root);
// 抢,然后去下下家
int do_it = root.val
+ (root.left == null ?
0 : rob(root.left.left) + rob(root.left.right))
+ (root.right == null ?
0 : rob(root.right.left) + rob(root.right.right));
// 不抢,然后去下家
int not_do = rob(root.left) + rob(root.right);

int res = Math.max(do_it, not_do);
memo.put(root, res);
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int rob(TreeNode root) {
int[] res = dp(root);
return Math.max(res[0], res[1]);
}

/* 返回一个大小为 2 的数组 arr
arr[0] 表示不抢 root 的话,得到的最大钱数
arr[1] 表示抢 root 的话,得到的最大钱数 */
int[] dp(TreeNode root) {
if (root == null)
return new int[]{0, 0};
int[] left = dp(root.left);
int[] right = dp(root.right);
// 抢,下家就不能抢了
int rob = root.val + left[0] + right[0];
// 不抢,下家可抢可不抢,取决于收益大小
int not_rob = Math.max(left[0], left[1])
+ Math.max(right[0], right[1]);

return new int[]{not_rob, rob};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def rob(self, root: TreeNode) -> int:
res=self.dp(root)
return max(res[0],res[1])

def dp(self,root):
if not root:
return (0,0)
left=self.dp(root.left)
right=self.dp(root.right)
rob=root.val+left[0]+right[0]
not_rob=max(left[0],left[1])+max(right[0],right[1])
return (not_rob,rob)
支持,让我的文章更加优秀!