小学生都能看懂的题解 | #打家劫舍(一)#
问题描述
想象一下,你是一个小偷,准备去偷邻街的房子。每个房子里有一些钱,但是你不能同时偷相邻的两个房子。比如,如果你偷了第一间房子,就不能再偷第二间;如果偷了第二间,你就不能偷第一间和第三间。
给你一个数组,每个数字代表一个房子里有多少钱。我们的目标是找到一个偷钱的计划,让你偷到的钱最多。
解决方案
为了找到最好的计划,我们可以使用一种叫做动态规划的技巧。这个技巧可以帮助我们一步一步地解决问题,直到我们找到答案。
-
定义一个数组:我们用一个数组来存储每一步能偷到的最多钱。
dp[i]
表示偷到第i
间房子时,能偷到的最多钱。
-
决策:对于每一间房子,我们有两个选择:
- 不偷第
i
间房子,那么最多的钱就是dp[i-1]
(也就是偷到前一间房子时的钱)。 - 偷第
i
间房子,那么最多的钱就是nums[i]
(第i
间房子里的钱)加上dp[i-2]
(也就是偷到前两间房子时的钱,因为不能偷相邻的房子)。
所以,我们的公式就是: [ dp[i] = \max(dp[i-1], nums[i] + dp[i-2]) ]
- 不偷第
-
初始化:
- 如果没有房子,最多的钱是0。
- 如果只有一个房子,最多的钱就是这个房子里的钱。
- 如果有两个房子,最多的钱就是这两个房子中较多的那一个。
-
遍历房子:从第三间房子开始,按照公式一步步计算,直到最后一间房子。
-
返回结果:最后返回最后一间房子能偷到的最多钱。
代码解释
下面是实现这个方案的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;
}
}
代码步骤解释
-
类定义:我们定义了一个叫
HouseRobber
的类,这个类里面有一个方法rob
,用来计算最多能偷到的钱。 -
输入检查:
- 如果没有房子(数组为空),直接返回0。
- 如果只有一个房子,返回那个房子里的钱。
-
初始化:
prev1
保存第一个房子的金额。prev2
保存前两个房子中最多的金额。
-
遍历房子:
- 从第三间房子开始,使用循环来计算当前能偷到的最多钱。
- 更新
prev1
和prev2
,以便下次循环使用。
-
返回结果:最后返回
prev2
,它存储着偷到的最多金额。
例子说明
- 对于输入
[1, 2, 3, 4]
,最优的偷窃方式是偷第2(2元)和第4(4元)个房子,所以总共是6
。 - 对于输入
[1, 3, 6]
,最优的方式是偷第1(1元)和第3(6元)个房子,总共是7
。 - 对于输入
[2, 10, 5]
,最优的方式是偷第2(10元)个房子,结果是10
。
这样,通过一步一步的计算,我们就找到了偷到最多钱的计划! 希望这篇文章能够帮到你👍。
#题解#小学生都能看懂的算法 文章被收录于专栏
主要面向小白的算法文章。以小学生都能看懂为目标而编写,顺便巩固下自己。