LeetCode198：打家劫舍

要求—

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

题目解析—

如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。所以必不能取相邻元素的金额；
而且数组元素是非负的

思路—

动态规划的的四个解题步骤是：
定义子问题
写出子问题的递推关系
确定 DP 数组的计算顺序
空间优化（可选）这个新手可以不做，以后优化代码时在看

步骤一：定义子问题

子问题是和原问题相似，但规模较小的问题，例如这道小偷问题，原问题是“从全部房子中能偷到的最大金额”，将问题的规模缩小，子问题就是“从 k 个房子中能偷到的最大金额”，用 f(k)表示；k代表单个房子

子问题是参数化，定义的子问题中有参数k，假设有n个房子，就一共有n个子问题；动态规划实际上就是通过求这一堆子问题的解，求出原问题的解。这要求子问题需要具备两个性质：

• 原问题要能由子问题表示，例如这道小偷问题，k=n时实际上就是原问题。
• 一个子问题要能由其他子问题的解求出，例如这道小偷问题中，f(k) 可以由f(k-1) 和 f(k-2)解出；

步骤二：写出子问题的递推关系

假设一共有n个房子，每个房子的金额分别是H₀，H₁，…，Hn-₁，子问题f(k)表示从前k个房子(H₀，H₁，…，Hk-₁)中能偷到的最大金额。前提声明，这里偷k-1间房子，不是都偷奥，还得按题目要求走

k 个房子中最后一个房子是 Hk−1​ 。如果不偷这个房子，那么问题就变成在前 k−1 个房子中偷到最大的金额，也就是子问题 f(k-1)。如果偷这个房子，那么前一个房子Hk−2显然不能偷，其他房子不受影响。那么问题就变成在前 k−2 个房子中偷到的最大的金额。两种情况中，选择金额较大的一种结果。

需要注意的是：

• 当k=0时，代表没有房子，直接返回f(0) = 0;
• 当k=1时，只有一个房子，就偷这个，不能白来不是，f(1) = H₀;

步骤三：确定dp数组的计算顺序

建议自底向上的、使用dp数组的循环方法；但有另一种方法：自顶向下，备忘录递归的方式；
dp数组也叫子问题数组，因为dp数组中每个元素对应一个子问题，如下图所示，dp[k]对应子问题f[k]，即偷前k间房子的最大金额。

我们发现每个f(k)依赖f(k-1) 和 f(k-2)，所以，dp[k] 依赖 dp[k-1] 和 dp[k-2]；既然 dp 数组中的依赖关系都是向右指的，dp数组的计算顺序就是从左向右。这样我们可以保证，计算一个子问题的时候，它所依赖的那些子问题已经计算出来了。

public class LeetCode198 {
    public int rob(int[] nums) {
        //如果没有房子，返回0；如果只有一个房子，返回当前房子的金额即可
        if (nums.length == 0){
            return 0;
        }
        if (nums.length == 1){
            return nums[0];
        }

        //定义一个dp数组，这里长度+1，是为了避免下面dp[i-2]超出边界
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        //这里需要注意一下，dp数组下标和nums数组下标差1；并不是对应的，避免下面循环的代码理解出错
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            //这里nums[i-1]对应dp[i],如果看不懂，可以看上面定义的dp数组和nums数组的关系；
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return dp[nums.length];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22