[数据结构与算法]LeetCode 198. 打家劫舍【c++/java详细题解】

1、题目

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

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

示例 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.length <= 100
• 0 <= nums[i] <= 400

2、思路

(动态规划) $O(n)$

状态表示：f[i]表示偷窃1号到i号房间所能获得的最高金额。那么，f[n]就表示偷窃1号到n号房间所能获得的最高金额，即为答案。

状态计算：

假设有i间房间，考虑最后一间偷还是不偷房间，有两种选择方案：

• 1、偷窃前i-1间房间，不偷窃最后一间房间，那么问题就转化为了偷窃1号到i - 1号房间所能获得的最高金额，即f[i] = f[i-1]。

• 2、偷窃前i - 2间房间和最后一间房间 (相邻的房屋不可闯入)，那么问题就转化为了偷窃1号到i - 2号房间所能获得的最高金额再加上偷窃第i号房间的金额，即f[i] = f[i - 2] + nums[i]。 (下标均从1开始)

两种方案，选择其中金额最大的一个。因此状态转移方程为： f[i] = max(f[i - 1], f[i - 2] + nums[i])。 (下标均从1开始)

初始化：f[1] = nums[0]，偷窃1号房间所能获得的最高金额为nums[0]。

实现细节：

我们定义的状态表示f[]数组和nums[]数组下标均是从1开始的，而题目给出的nums[]数组下标是从0开始的。为了一 一对应，状态转移方程中的nums[i]的值要往前错一位，取nums[i-1]，这点细节希望大家可以注意一下。

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

3、c++代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size() ;
        vector<int>f(n + 1);
        f[1] = nums[0];  //初始化
        for(int i = 2; i <= n; i++){
            int w = nums[i - 1];
            f[i] = max(f[i-1], f[i - 2] + w); //状态转移方程
        }
        return f[n];
    }
};

4、java代码

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        f[1] = nums[0];  //初始化
        for(int i = 2; i <= n; i++){
            int w = nums[i - 1];
            f[i] = Math.max(f[i-1], f[i - 2] + w);  //状态转移方程
        }
        return f[n];
    }
}

原题链接： 198. 打家劫舍