这两天在学习的时候，发现有个打家劫舍的题目，有意思的很,分享给大家。
基础题目
题目内容
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 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
题解
/*
使用动态规划，简单
*/
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n==1){
return nums[0];
}
// f[i]表示进入第i个门能偷取到的最大金额
int[] f = new int[n];
f[0]=nums[0];
f[1]=Math.max(nums[0],nums[1]);
for(int i = 2;i<n;i++){
f[i]=Math.max(f[i-2]+nums[i],f[i-1]);
}
return f[n-1];
}
}
进阶题目1
213. 打家劫舍 II
在上一题的基础上，加了个条件 这些房子首尾相连 ，这就涉及到第一个房子选与不选的问题，给f数组加一个维度，来表示第一个房子是否选择。
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n==1 ){
return nums[0];
}else if (n==2){
return Math.max(nums[0],nums[1]);
}
// f[i][0]表示进入第1个门时，进入第i个门能偷取到的金额
// f[i][1]表示不进入第1个门时，进入第i个门能偷取到的金额
int[][] f = new int[n][2];
f[0][0]=0;
f[0][1]=nums[0];
f[1][0]=nums[1];
f[1][1]=nums[0];
for(int i = 2;i<n;i++){
for(int j = 0;j<=1;j++){
if(i==n-1 && j==1){
// 最后一个元素取了，第一个元素没取
f[i][j]=f[i-1][j];
}else{
// 其他情况，非环形处理
f[i][j]=Math.max(f[i-2][j]+nums[i],f[i-1][j]);
}
}
}
return Math.max(f[n-1][0],f[n-1][1]);
}
}
进阶题目2
337. 打家劫舍 III
这是一个树形的题目，具体可看题目介绍，也是动态规划的思想来解决。
class Solution {
public int rob(TreeNode root) {
int[] rootStatus = dfs(root);
return Math.max(rootStatus[0], rootStatus[1]);
}
public int[] dfs(TreeNode node) {
if (node == null) {
return new int[]{0, 0};
}
int[] l = dfs(node.left);
int[] r = dfs(node.right);
//选中当前节点时，值为左右子节点不选中的状态之和
int selected = node.val + l[1] + r[1];
// 不选中当前节点时，值为左右节点中两种状态的最大值之和
int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{selected, notSelected};
}
}
``
评论区