打家劫舍问题

2021-08-18

打家劫舍 1

问题描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

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

问题分析

$dp$ 数组定义

对于每一间房屋，有偷和不偷两种选择。如果选择偷第 $i$ 间房屋，那么就必然不能偷第 $i - 1$ 间房屋，如果选择不偷第 $i$ 间房屋，就可以选择偷第 $i - 1$ 间房屋，显然要取两者的最大值。所以定义数组 $dp$，$dp[i]$ 表示在 $0$ ~ $i$ 间房屋内能偷到的最大金额。

递推公式

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

初始化

边界条件就是对于第一间房屋的选择，后面每一个节点的状态都是由前面的状态转化来的。所以初始化 $dp[0]$，然后从前向后依次遍历。

1 2	dp[0] = nums[0] //偷第一间 dp[1] = max(num[0], nums[1]) //偷不偷第二间取决于两件房屋的最大收益是哪个

golang 代码实现

func rob(nums []int) int {
    if len(nums) <= 1 {
        return nums[0]
    }
    //dp[i]代表从num[0]到nums[i]实施盗窃，最大能盗窃的价值
    dp := make([]int, len(nums))
    //初始化边界，dp[0]自然就只能盗窃nums[0]
    dp[0] = nums[0]
    //dp[1]只可能是nums[0]和nums[1]中的最大值（盗窃0或盗窃1）
    dp[1] = max(nums[0], nums[1])
    for i := 2; i < len(nums); i++ {
        //从i=2开始遍历
        //对于dp[i]有两种情况推导：
        //1 盗窃nums[i]，那么就是在dp[i - 2]（nums[0]到nums[i-2]能盗窃的最大值）加上nums[i]
        //2 不盗窃nums[i]，那么dp[i]就等于dp[i - 1]
      dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
  }

    return dp[len(dp)-1]
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$，可以利用滚动数组优化空间复杂度至 $O(1)$。

打家劫舍 2

问题描述

leetcode 213

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

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

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

问题分析

与第 $1$ 题的唯一区别就是现在的房屋连成了环形，也就是边界位置不固定了，原本数组的第一个位置就是边界。所以不能像上一题一样整个房屋数组统一处理，因为在考虑最后一个房屋时，它的与偷不偷不仅仅只受前面选择的影响，也同样影响着第一间房屋的选择。可以先考虑偷 $0$ ~ $n-1$ 间翻屋，再考虑偷 $1$ ~ $n$ 间房屋，两者再取最大值。这样实际就将环形房屋的首尾切割开了。

$\begin{array}{|c|c|} \hline 2&3\\ \hline \end{array}$

先在前两间房屋内选择，偷第二间屋子收益最多，为 $3$。

$\begin{array}{|c|c|} \hline 3&2\\ \hline \end{array}$

然后在后两间房屋内选择，偷第二间屋子最多，为 $3$。所以最大值就是三。这也就时本题与第 $1$ 题的唯一区别，$dp$ 数组的下标定义、递推公式、初始化、遍历顺序等都与第 $1$ 题完全相同。

golang 代码实现

func rob(nums []int) int {
    if len(nums) <= 1 {
        return nums[0]
    }
    if len(nums) == 2 {
        return max(nums[0], nums[1])
    }
    return max(_rob(nums[:len(nums)-1]), _rob(nums[1:]))
}

func _rob(nums []int) int {
    //dp[i]代表从num[0]到nums[i]实施盗窃，最大能盗窃的价值
    dp := make([]int, len(nums))
    //初始化边界，dp[0]自然就只能盗窃nums[0]
    dp[0] = nums[0]
    //dp[1]只可能是nums[0]和nums[1]中的最大值（盗窃0或盗窃1）
    dp[1] = max(nums[0], nums[1])
    for i := 2; i < len(nums); i++ {
        //从i=2开始遍历
        //对于dp[i]有两种情况推导：
        //1 盗窃nums[i]，那么就是在dp[i - 2]（nums[0]到nums[i-2]能盗窃的最大值）加上nums[i]
        //2 不盗窃nums[i]，那么dp[i]就等于dp[i - 1]
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    }
    return dp[len(dp) - 1]
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$，可以利用滚动数组优化空间复杂度至 $O(1)$。

打家劫舍 3

问题描述

leetcode 337

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

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

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

     3
    / \
   2   3
    \   \ 
     3   1

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

问题分析

第 $1$ 题中房屋是线性的，第 $2$ 题中房屋是环形的，都是确定了一个边界位置之后开始依次向后推导的。但是本题中房屋排布成树形结构，难点就是边界位置的确定。显然对于一颗树来说，边界位置就应该是叶子结点。那么对于每一个非叶子结点，它的状态就应该依赖于两个叶子结点的状态来算出，所以本题树的遍历顺序为后序遍历。

给每一个结点定义一个长度为 $2$ 的数组，索引 $0$ 表示不偷偷该结点，索引 $1$ 表示偷该结点。对于空结点 nil，数组两个索引位置的值均为 $0$。

graph TB
    A(("3 [6, 7]"))
    B(("2 [3, 2]"))
    C(("3 [1, 3]"))
    D(("3 [0, 3]"))
    E(("1 [0, 1]"))
    F(("nil [0, 0]"))
    G(("nil [0, 0]"))

    A-->B
    A-->C
    B-->F
    B-->D
    C-->G
    C-->E

如上图所示，从根结点开始后序遍历。直到遍历到空结点 nil，空结点返回的数组，值如下（空结点，偷与不偷抢都必然是 $0$），这是本题最重要的边界条件。

1	return [2]int{0, 0}

而非空结点，就可以根据它的两个子结点的选择情况，来计算自己在偷与不偷两种状态下能获取的最大收益：

偷当前结点：则一定不能偷它的子结点，等于【当前结点值】+【不偷左子结点的收益】+【不偷右子结点的收益】
不偷当前结点：则可以选择偷它的子结点（也可以不偷），所以就等于【左子结点偷和不偷的最大值】+【右子结点偷和不偷的最大值】

这样经过后序遍历递归处理了整颗树后，根结点偷和不偷的最大值就是题目答案。

golang 代码实现

func rob(root *TreeNode) int {
    r := _rob(root)
    return max(r[0], r[1])
}

func _rob(node *TreeNode) [2]int {
    //节点为空，偷与不偷都是0
    if node == nil {
        return [2]int{}
    }

    robleft := _rob(node.Left)
    robright := _rob(node.Right)
    //不偷当前节点，那么他的两个子节点可偷可不偷，所以各取偷与不偷的最大值
    val1 := max(robleft[0], robleft[1]) + max(robright[0], robright[1])
    //偷当前节点，则必然不能偷他的两个子节点
    val2 := node.Val + robleft[0] + robright[0]

    return [2]int{val1, val2}
}

要遍历一遍树的所有结点，所以时间复杂度 $O(n)$，空间复杂度 $O(1)$。