小学生都能看懂的题解 | #打家劫舍(一)#

问题描述

想象一下,你是一个小偷,准备去偷邻街的房子。每个房子里有一些钱,但是你不能同时偷相邻的两个房子。比如,如果你偷了第一间房子,就不能再偷第二间;如果偷了第二间,你就不能偷第一间和第三间。

给你一个数组,每个数字代表一个房子里有多少钱。我们的目标是找到一个偷钱的计划,让你偷到的钱最多。

解决方案

为了找到最好的计划,我们可以使用一种叫做动态规划的技巧。这个技巧可以帮助我们一步一步地解决问题,直到我们找到答案。

  1. 定义一个数组:我们用一个数组来存储每一步能偷到的最多钱。

    • dp[i]表示偷到第i间房子时,能偷到的最多钱。
  2. 决策:对于每一间房子,我们有两个选择:

    • 不偷第i间房子,那么最多的钱就是dp[i-1](也就是偷到前一间房子时的钱)。
    • 偷第i间房子,那么最多的钱就是nums[i](第i间房子里的钱)加上dp[i-2](也就是偷到前两间房子时的钱,因为不能偷相邻的房子)。

    所以,我们的公式就是: [ dp[i] = \max(dp[i-1], nums[i] + dp[i-2]) ]

  3. 初始化

    • 如果没有房子,最多的钱是0。
    • 如果只有一个房子,最多的钱就是这个房子里的钱。
    • 如果有两个房子,最多的钱就是这两个房子中较多的那一个。
  4. 遍历房子:从第三间房子开始,按照公式一步步计算,直到最后一间房子。

  5. 返回结果:最后返回最后一间房子能偷到的最多钱。

代码解释

下面是实现这个方案的Java代码:

public class HouseRobber {
    public int rob(int[] nums) {
        // 如果没有房子,返回0
        if (nums == null || nums.length == 0) {
            return 0; 
        }
        
        // 如果只有一个房子,返回那个房子里的钱
        if (nums.length == 1) {
            return nums[0]; 
        }
        
        // 初始化前两个状态
        int prev1 = nums[0]; // 第一个房子的最多钱
        int prev2 = Math.max(nums[0], nums[1]); // 前两个房子的最多钱
        
        // 从第三间房子开始计算
        for (int i = 2; i < nums.length; i++) {
            // 当前的最多钱是前两个选择的最大值
            int current = Math.max(prev2, nums[i] + prev1);
            // 更新前两个状态
            prev1 = prev2; // 更新为前一间
            prev2 = current; // 更新为当前最大值
        }
        
        // 返回最终的最大值
        return prev2; 
    }
}

代码步骤解释

  1. 类定义:我们定义了一个叫HouseRobber的类,这个类里面有一个方法rob,用来计算最多能偷到的钱。

  2. 输入检查

    • 如果没有房子(数组为空),直接返回0。
    • 如果只有一个房子,返回那个房子里的钱。
  3. 初始化

    • prev1保存第一个房子的金额。
    • prev2保存前两个房子中最多的金额。
  4. 遍历房子

    • 从第三间房子开始,使用循环来计算当前能偷到的最多钱。
    • 更新prev1prev2,以便下次循环使用。
  5. 返回结果:最后返回prev2,它存储着偷到的最多金额。

例子说明

  • 对于输入[1, 2, 3, 4],最优的偷窃方式是偷第2(2元)和第4(4元)个房子,所以总共是6
  • 对于输入[1, 3, 6],最优的方式是偷第1(1元)和第3(6元)个房子,总共是7
  • 对于输入[2, 10, 5],最优的方式是偷第2(10元)个房子,结果是10

这样,通过一步一步的计算,我们就找到了偷到最多钱的计划! 希望这篇文章能够帮到你👍。

#题解#
小学生都能看懂的算法 文章被收录于专栏

主要面向小白的算法文章。以小学生都能看懂为目标而编写,顺便巩固下自己。

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务