「图解大厂面试高频算法题」动态规划-打家劫舍I

PS: 本文为「图解大厂面试高频算法题」专题，主旨是根据“二八法则”的原理，以付出20%的时间成本，获得80%的刷题的收益，让那些想进互联网大厂的人少走些弯路。

PS: 欢迎关注我获取更多大厂面试总结。

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

在LeetCode官网中看到了这样的一个评论

金刀表示世上还是好人多，这位好孩子虽然输了题目，甚至在面试中挂了，但是但是赢了人生哈哈。
甚至有网友表示


如果你是小偷，你怎样才能偷最多的钱呢？

题目介绍

题目解答

这题粗略一看，估计又是一道动态规划题型。有一句话说得好，万事开头难，在动态规划题型中，找出子问题是最关键的，毕竟全局解是一步一步求解子问题来得到的。如果子问题是什么都不知道，那咋求出全局解呢。

寻找子问题

我们先来看看如何寻找子问题。题目的大意是求解从N个房子中能偷取到的最大的金额，这个问题是不是可以拆成N个子问题？

• 从1个房子中能偷取到的最大的金额是多少？
• 从2个房子中能偷取到的最大的金额是多少？
• …
• 从N-1个房子中能偷取到的最大的金额是多少？
• 从N个房子中能偷取到的最大的金额是多少？
  
  注意这题有一个限制就是小偷不能连续偷两个相邻的房子，所以小偷经过一个房子时，他需要思考偷还是不偷，这样每一个子问题又可以继续拆解变成2N个子问题：
• 从1个房子中能偷取到的最大的金额是多少？
  • 不偷第1个房子时，能偷取到的最大的金额是多少？
  • 偷第1个房子时，能偷取到的最大的金额是多少？
• 从2个房子中能偷取到的最大的金额是多少？
  • 不偷第2个房子时，能偷取到的最大的金额是多少？
  • 偷第2个房子时，能偷取到的最大的金额是多少？
• … …
• 从N-1个房子中能偷取到的最大的金额是多少？
  • 不偷第N-2个房子时，能偷取到的最大的金额是多少？
  • 偷第N-2个房子时，能偷取到的最大的金额是多少？
• 从N个房子中能偷取到的最大的金额是多少？
  • 不偷第N-1个房子时，能偷取到的最大的金额是多少？
  • 偷第N-1个房子时，能偷取到的最大的金额是多少？
    

确定状态转移方程

子问题已经确定出来了，那么如果我们知道了从N-1个房子中能偷取到的最大的金额，那么我们如何根据这个子问题来算出从N个房子中能偷取到的最大的金额原问题呢？

小偷为了能偷最多的钱，自学了编程然后搞了两个数组steal和not_steal，steal[k]记录小偷偷了第K个房子时能获取到的最多的钱，not_steal[k]记录小偷不偷第K个房子时能获取到的最多的钱，小偷每到达一个房子的时候，都会去更新steal[k]和not_steal[k]，当小偷来到了第K个房子的时心里可能这么想：

• 如果第K-1个房子已经偷了，那第K个房子就不能偷了，不然该报警了。
  • 所以小偷决定不偷第K个房子，并记录下当前不偷第K个房子时总共能获取到的最大的金额为not_steal[k] = max(steal[k-1], not_steal[k-1]) 。
  • 解释: 既然不能偷第K个房子了，那小偷可以偷第K-1一个房子(steal[k-1])，也可以不偷第K-1个房子(not_steal[k-1])，小偷当然要选择steal[k-1]和not_steal[k-1]这两个数其中最大的一个。
• 如果第K-1个房子没有偷，那可以偷第K个房子也可以不偷第K个房子。
  • 小偷决定不偷第K个房子，并记录下当前不偷第K个房子时总共能获取到的最大的金额同上。
  • 小偷决定偷第K个房子，那么小偷当前偷第K个房子时总共能获取到的最大的金额为steal[k] = not_steal[k-1] + nums[k]。
    • 解释: 既然决定偷第K个房子了，那小偷不可以偷第K-1个房子(not_steal[k-1])，所以小偷偷完第K个房子(steal[k])后获取到的最大金额为当前房屋价值再加上not_steal[k-1]。
      状态转移方程就确定下来了：
• not_steal[k] = max(steal[k-1], not_steal[k-1])
• steal[k] = not_steal[k-1] + nums[k]

状态转移方程在动态规划里是最核心的概念，有了状态转移方程，那么就已经有了题目的答案了，剩下的就交给代码来实现了。

方法一：一维动态规划

代码实现

class Solution {
    public int rob(int[] nums) {
        int[][] dp = new int[nums.length+1][2];
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = dp[i-1][1] + nums[i-1]; // 0 - 表示steal[k]
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]); // 1 - 表示not_steal[k]
        }
        return Math.max(dp[nums.length][0], dp[nums.length][1]);
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
• 空间复杂度：O(n)。

方法二：优化动态规划

上面的一维动态规划解法使用了一个dp数组，我们仔细观察可以发现，计算dp[i]的状态只取决于dp[i-1]的状态，所以我们可以用两个临时变量steal和not_steal来代替dp[i-1][0]和dp[i-1][1]中的值。

代码实现

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int steal = nums[0], not_steal = 0;
        for (int i = 1; i < nums.length; i++) {
            int new_steal = not_steal + nums[i];
            int new_not_steal = Math.max(steal, not_steal);
            steal = new_steal;
            not_steal = new_not_steal;
        }
        return Math.max(steal, not_steal);
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
• 空间复杂度：O(1)。

总结

算法好的人，当小偷偷的钱都是最多的，你说算法重要不重要？？？