198.打家劫舍

LeetCode LeetCode 热题100 数组动态规划

发布时间 : 2000-01-10 01:09

字数:2.3k 阅读 :

评论:

198.打家劫舍

198.打家劫舍

198.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

198.2 题解

方法一：动态规划

思路

经典的动态规划问题。定义 dp[i] 为前 i 间房屋能偷到的最高金额。

对于第 i 间房屋，有两个选择：

偷：不能偷第 i-1 间，金额 = dp[i-2] + nums[i]
不偷：金额 = dp[i-1]

取两者最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

举个例子：nums = [2,7,9,3,1]

dp[0] = 2（只能偷第1间）
dp[1] = max(2, 7) = 7（偷第2间更划算）
dp[2] = max(7, 2+9) = 11（偷第1、3间）
dp[3] = max(11, 7+3) = 11（不偷第4间）
dp[4] = max(11, 11+1) = 12（偷第1、3、5间）

复杂度分析

时间复杂度：O(n)，遍历一次数组
空间复杂度：O(n)，dp 数组

代码

// 方法一：动态规划
// 使用一个数组 dp，dp[i] 表示在第 i 个房屋能够偷窃到的最高金额
// 偷窃第 k 间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2 间房屋的最高总金额与第 k间房屋的金额之和
// 不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额
// 第i个房屋能偷到的最大值是
// dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) 
static int Rob1(int[] nums)
{
    // 获取输入数组的长度
    int numsLength = nums.Length;

    // 如果数组为空，返回偷窃金额为 0
    if (numsLength == 0)
        return 0;

    // 如果数组只有一个元素，直接返回该元素的值
    if (numsLength == 1)
        return nums[0];

    // 创建一个数组 dp 用于存储偷窃到每个房屋的最高金额
    int[] dp = new int[numsLength];

    // 初始化前两个房屋的偷窃金额
    dp[0] = nums[0];
    dp[1] = Math.Max(nums[0], nums[1]);

    // 从第三个房屋开始，迭代计算每个房屋的最高偷窃金额
    for (int i = 2; i < numsLength; i++)
    {
        // 在当前房屋偷窃和不偷窃之间选择最大的金额
        dp[i] = Math.Max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    // 返回最后一个房屋的最高偷窃金额
    return dp[numsLength - 1];
}

方法二：滚动数组优化

思路

观察状态转移方程：dp[i] 只依赖 dp[i-1] 和 dp[i-2]，不需要整个数组。

用两个变量 prev2 和 prev1 分别表示 dp[i-2] 和 dp[i-1]，每次迭代更新即可。

举个例子：nums = [2,7,9,3,1]

prev2=0, prev1=0
i=0：curr=max(0, 0+2)=2，prev2=0, prev1=2
i=1：curr=max(2, 0+7)=7，prev2=2, prev1=7
i=2：curr=max(7, 2+9)=11，prev2=7, prev1=11
i=3：curr=max(11, 7+3)=11，prev2=11, prev1=11
i=4：curr=max(11, 11+1)=12，返回12

复杂度分析

时间复杂度：O(n)，遍历一次数组。
空间复杂度：O(1)，只使用两个变量。

// 方法二：滚动数组
// 优化空间复杂度，只需维护两个变量 cur 和 pre，分别表示当前房屋和前一个房屋的最高金额
// 大致思路和动态规划一样
static int Rob2(int[] nums)
{
    // 获取输入数组的长度
    int numsLength = nums.Length;

    // 如果数组为空，返回偷窃金额为 0
    if (numsLength == 0)
        return 0;

    // 如果数组只有一个元素，直接返回该元素的值
    if (numsLength == 1)
        return nums[0];

    // 初始化两个变量 pre 和 cur，分别表示前一个房屋和当前房屋的最高金额
    int pre = nums[0];
    int cur = Math.Max(nums[0], nums[1]);

    // 从第三个房屋开始，迭代计算每个房屋的最高偷窃金额
    for (int i = 2; i < numsLength; i++)
    {
        // 使用临时变量保存当前房屋的最高金额
        int temp = cur;

        // 更新当前房屋的最高金额，选择在当前房屋偷窃和不偷窃之间的最大值
        cur = Math.Max(cur, pre + nums[i]);

        // 更新前一个房屋的最高金额为上一次迭代的当前房屋的最高金额
        pre = temp;
    }

    // 返回最后一个房屋的最高偷窃金额
    return cur;
}

198.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

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

        // 示例 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

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = {1, 2, 3, 1};
        int result1 = Rob1(nums1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = Rob2(nums1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] nums2 = {2, 7, 9, 3, 1};
        int result2 = Rob1(nums2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = Rob2(nums2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：动态规划
    // 使用一个数组 dp，dp[i] 表示在第 i 个房屋能够偷窃到的最高金额
    // 偷窃第 k 间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2 间房屋的最高总金额与第 k间房屋的金额之和
    // 不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额
    // 第i个房屋能偷到的最大值是
    // dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) 
    static int Rob1(int[] nums)
    {
        // 获取输入数组的长度
        int numsLength = nums.Length;

        // 如果数组为空，返回偷窃金额为 0
        if (numsLength == 0)
            return 0;

        // 如果数组只有一个元素，直接返回该元素的值
        if (numsLength == 1)
            return nums[0];

        // 创建一个数组 dp 用于存储偷窃到每个房屋的最高金额
        int[] dp = new int[numsLength];

        // 初始化前两个房屋的偷窃金额
        dp[0] = nums[0];
        dp[1] = Math.Max(nums[0], nums[1]);

        // 从第三个房屋开始，迭代计算每个房屋的最高偷窃金额
        for (int i = 2; i < numsLength; i++)
        {
            // 在当前房屋偷窃和不偷窃之间选择最大的金额
            dp[i] = Math.Max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        // 返回最后一个房屋的最高偷窃金额
        return dp[numsLength - 1];
    }

    // 方法二：滚动数组
    // 优化空间复杂度，只需维护两个变量 cur 和 pre，分别表示当前房屋和前一个房屋的最高金额
    // 大致思路和动态规划一样
    static int Rob2(int[] nums)
    {
        // 获取输入数组的长度
        int numsLength = nums.Length;

        // 如果数组为空，返回偷窃金额为 0
        if (numsLength == 0)
            return 0;

        // 如果数组只有一个元素，直接返回该元素的值
        if (numsLength == 1)
            return nums[0];

        // 初始化两个变量 pre 和 cur，分别表示前一个房屋和当前房屋的最高金额
        int pre = nums[0];
        int cur = Math.Max(nums[0], nums[1]);

        // 从第三个房屋开始，迭代计算每个房屋的最高偷窃金额
        for (int i = 2; i < numsLength; i++)
        {
            // 使用临时变量保存当前房屋的最高金额
            int temp = cur;

            // 更新当前房屋的最高金额，选择在当前房屋偷窃和不偷窃之间的最大值
            cur = Math.Max(cur, pre + nums[i]);

            // 更新前一个房屋的最高金额为上一次迭代的当前房屋的最高金额
            pre = temp;
        }

        // 返回最后一个房屋的最高偷窃金额
        return cur;
    }



    #endregion
}

198.4 运行结果

示例1 方法1 输出：4
示例1 方法2 输出：4
示例2 方法1 输出：12
示例2 方法2 输出：12

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com