1. question: 打家劫舍(中等)
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/house-robber
示例 1:
1 2 3 4
| 输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
|
示例 2:
1 2 3 4
| 输入:[2,7,9,3,1] 输出:12 解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
|
提示:
1 2
| 1 <= nums.length <= 100 0 <= nums[i] <= 400
|
2. answers
这道题最开始想用背包问题解决,发现绕进去了。其实没必要,参考了题解。在以本元素X为结尾的房屋序列所能形成的最大值仅取决于【以X-1结尾的最大值,以X-2结尾的最大值+本元素】
正序看一下:
- 只有元素【0】时,显然最大值就是【0】
- 当有元素【0,1】时,显然最大值就是max(0,1)
- 当有元素【0,1,2】时,显然是max(1, 0+2)
- 当有元素【0,1,2,3】时,显然max(2, 1+3)
因此,定义数组dp[i],保存以当前元素结尾的所有元素形成的最大值。代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| public class Solution_0129_02 {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0]; dp[1] = Math.max(dp[0], nums[1]);
for (int i = 2; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); }
return dp[nums.length - 1]; } }
|
因为我们在计算当前元素时,仅用到了前两个元素,因此,可直接用两个空间来保存,减少空间开销。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| public class Solution_0129_03 {
public int rob(int[] nums) {
if(nums.length == 1) return nums[0];
int[] dp = new int[2];
dp[0] = nums[0]; dp[1] = Math.max(dp[0], nums[1]);
int temp;
for (int i = 2; i < nums.length; i++) {
if(dp[0] + nums[i] > dp[1]) {
temp = dp[1]; dp[1] = dp[0] + nums[i]; dp[0] = temp;
} else { dp[0] = dp[1]; } }
return dp[1]; }
public static void main(String[] args) { System.out.println();
Solution_0129_03 s = new Solution_0129_03();
int[] nums = {1, 2, 3, 1};
System.out.println(s.rob(nums)); } }
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。