LeetCode 198、 打家劫舍

视频地址：LeetCode 198、 打家劫舍

一、题目描述

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

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

示例 1：

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

二、题目解析

三、参考代码 （吴师兄）

dp数组长度为n+1的写法

1、Java 代码

class Solution {
    public int rob(int[] nums) {
        
        // 先获取全部房间的总数
        int n = nums.length;

        // 如果数组为空，表示没有房间，那么自然偷不到东西，直接返回 0
        if(n == 0) return 0;

        // 如果数组只有 1 个元素，表示只有 1 个房间，那么只能偷这个房间的东西，直接返回这个房间的金额
        if(n == 1) return nums[0];

        // 设置一个数组 value 用来存放前 n 个房间可以偷取的最大金额
        // value[0] 表示前 0 个房间可以偷取的最大金额
        // value[1] 表示前 1 个房间可以偷取的最大金额
        // value[i] 表示前 i 个房间可以偷取的最大金额
        int[] value = new int[n + 1];

        // value[0] 表示前 0 个房间可以偷取的最大金额
        // 0 个房间自然偷不到东西，所以存放结果为 0
        value[0] = 0;

        // value[1] 表示前 1 个房间可以偷取的最大金额
        // 只有 1 个房间，那么只能偷这个房间的东西，所以存放结果为这个房间的金额
        value[1] = nums[0];

        // 从 i = 2 直到 i = n，value 中存放的结果由前 i - 2 和 i - 1 共同决定
        for(int i = 2 ; i <= n ; i++){

            // 转移方程：value[i] 等于 value[ i - 1 ]  和 value[ i - 2 ] + num[ i - 1] 中的较大值
            value[i] = Math.max(value[i - 1] ,value[i - 2] + nums[i - 1]);
        }

        // 最后返回 value 的最后一个值
        return value[n];

    }
}

**2、**C++ 代码

class Solution {
public:
    int rob(vector<int>& nums) {
         // 先获取全部房间的总数
        int n = nums.size();

        // 如果数组为空，表示没有房间，那么自然偷不到东西，直接返回 0
        if(n == 0) return 0;

        // 如果数组只有 1 个元素，表示只有 1 个房间，那么只能偷这个房间的东西，直接返回这个房间的金额
        if(n == 1) return nums[0];

        // 设置一个数组 value 用来存放前 n 个房间可以偷取的最大金额
        // value[0] 表示前 0 个房间可以偷取的最大金额
        // value[1] 表示前 1 个房间可以偷取的最大金额
        // value[i] 表示前 i 个房间可以偷取的最大金额
        vector<int> value( n + 1 );

        // value[0] 表示前 0 个房间可以偷取的最大金额
        // 0 个房间自然偷不到东西，所以存放结果为 0
        value[0] = 0;

        // value[1] 表示前 1 个房间可以偷取的最大金额
        // 只有 1 个房间，那么只能偷这个房间的东西，所以存放结果为这个房间的金额
        value[1] = nums[0];

        // 从 i = 2 直到 i = n，value 中存放的结果由前 i - 2 和 i - 1 共同决定
        for(int i = 2 ; i <= n ; i++){

            // 转移方程：value[i] 等于 value[ i - 1 ]  和 value[ i - 2 ] + num[ i - 1] 中的较大值
            value[i] = max(value[i - 1] ,value[i - 2] + nums[i - 1]);
        }

        // 最后返回 value 的最后一个值
        return value[n];
    }
};

3、Python 代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 先获取全部房间的总数
        n = len(nums)

        # 如果数组为空，表示没有房间，那么自然偷不到东西，直接返回 0
        if n == 0 :  return 0

        # 如果数组只有 1 个元素，表示只有 1 个房间，那么只能偷这个房间的东西，直接返回这个房间的金额
        if n == 1 :  return nums[0]

        # 设置一个数组 value 用来存放前 n 个房间可以偷取的最大金额
        # value[0] 表示前 0 个房间可以偷取的最大金额
        # value[1] 表示前 1 个房间可以偷取的最大金额
        # value[i] 表示前 i 个房间可以偷取的最大金额
        value = [ 0 for _ in range( n + 1)]

        # value[0] 表示前 0 个房间可以偷取的最大金额
        # 0 个房间自然偷不到东西，所以存放结果为 0
        value[0] = 0

        # value[1] 表示前 1 个房间可以偷取的最大金额
        # 只有 1 个房间，那么只能偷这个房间的东西，所以存放结果为这个房间的金额
        value[1] = nums[0]

        # 从 i = 2 直到 i = n，value 中存放的结果由前 i - 2 和 i - 1 共同决定
        for i in range( 2 , n + 1 ) : 

            # 转移方程：value[i] 等于 value[ i - 1 ]  和 value[ i - 2 ] + num[ i - 1] 中的较大值
            value[i] = max(value[i - 1] ,value[i - 2] + nums[i - 1])
        

        # 最后返回 value 的最后一个值
        return value[n]

四、参考代码（许老师）

dp数组长度为n的写法

1、Java 代码

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        
        return dp[n - 1];
    }
}

2、C++ 代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for (int i = 2; i < n; ++i) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        
        return dp[n - 1];
    }
};

3、Python 代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp
        n = len(nums)
        dp = [0] * n
        if n <= 1:
            return max(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[1], nums[0])
        for i in range(2, n):
            # 进入/不进入
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        return dp[-1]