动态规划：打家劫舍
各位小伙伴，大家好！上周我们给出了一篇动态规划系列的字符串匹配。详情可以点击链接进行查看（动态规划：字符串匹配）~本周我们再推一篇动态规划的题目，LeetCode打家劫舍系列。
打家劫舍I
LeetCode198---打家劫舍I【简单】 题目描述
题目描述
给定一个数组，每个元素都是正整数，我们需要在不连续获取相邻元素的情况下，使得数组中总和最大的结果。
1、解题思路
这道题的难度级别被归类为简单题目也有一定的原因。根据题意，我们很容易得到动态规划的3个基本要素
- 动态规划的数组定义，
dp[i]的定义为：小偷在第i家时，能够获取的最大的金额。 - 在
dp[i]位置，小偷都可以有偷或者不偷的选择，- 当选择偷窃的时候，那么第
i-1家一定处于没有被偷窃的状态，此时状态转移方程：dp[i] = dp[i-2]+nums[i] - 当选择不偷窃的时候，此时
dp[i]的资产情况与dp[i-1]是相同的，所以此时的状态的方程为：dp[i]=dp[i-1] - 综上所述，我们的动态转移方程为：
dp[i] = max(dp[i-2] + nums[i] , dp[i-1])
- 当选择偷窃的时候，那么第
- 动态规划的初始条件：根据上面的动态方程可以发现，当我们把
i=0或者i=1带入的时候，会得到dp[-2]和dp[-1]的情况，这显然是不存在的，所以我们可以将不存在的情况设置为负无穷，所以就可以得到对应的初始条件- 对于第一个元素：
dp[0]=nums[0] - 对于第二个元素：
dp[1] = max(nums[0],nums[1])
- 对于第一个元素：
当动态规划的两个条件完成之后，我们就可以实现对应的代码了！
2、代码实现
public int rob(int[] nums) {
int len = nums.length;
//判断特殊情况
if(len < 1) return 0;
if(len == 1) return nums[0];
if(len == 2) return Math.max(nums[0],nums[1]);
//初始化
int[] ans = new int[len];
ans[0] = nums[0];
ans[1] = nums[0]>nums[1]?nums[0]:nums[1];
for(int i = 2 ; i < len ; i++){
//ans[i]可以分为两种，i-2时盗窃了，那么加上此次的盗窃，或者i-1时盗窃了，那么此次将无法继续盗窃
ans[i] = Math.max(ans[i-2]+nums[i],ans[i-1]);
}
return ans[len-1];
}打家劫舍II
Leetcode213 --- 打家劫舍II【中等题】 题目描述
题目描述
在上一道题的基础上，此题增加了一个新的条件，对于整个数组而言，我们需要认为数组的首尾是相互连接的。
1、解题思路
此时我们需要将整个数组分做情况来处理，具体的情况小白画了一个示意图给大家参考一下！
解题思路
主要有上面的三种情况可以取消环的限制。
- 第一种：去掉整个数组的两端，我们对整个数组只取
1~n-2的区域。 - 第二种：去掉数组的末尾，对数组的
0~n-2进行计算 - 第三种：去掉数组的开头，对数组的
1~n-1进行计算
然后我们再进行简化，由于当前数组的所有元素都是正整数，而情况二和情况三都包含了情况一，并且我们的目标是求取最大值，所以情况一的结果一定小于等于情况二和三。因此在编写实现代码的时候，我们就可以舍弃情况一，仅对后两种情况取最大值就可以了！
当我们计算后两种情况的时候，我们就又将其转化为了第一题的问题，然后直接套用第一题的代码即可！但是此处我们又进行了另一种优化。
代码优化
在上一题的代码中，我们发现在每次使用dp数组的时候，其实仅仅是使用i元素的前两个数值而已，分别是dp[i-2]和dp[i-1]，那么我们也可以对其进行简化，使用两个变量来分别代表这两个元素dp[i-2]和dp[i-1]。此时我们的空间复杂度将会从O(n)改变为O(1)。
2、代码实现
public int rob(int[] nums) {
//将整个环形分为两种情况来计算，从0~n-2和1~n-1
if(nums == null || nums.length == 0) return 0;
int len = nums.length ;
if(len == 1) return nums[0];
return Math.max(help(nums,0,len-2) , help(nums,1,len-1));
}
private int help(int[] nums , int start , int end){
int dpi1 = 0;
int dpi2 = 0;
int dpi = 0;
for(int i = end ; i >= start ; i--){
dpi = Math.max(nums[i] + dpi2 , dpi1);
dpi2 = dpi1;
dpi1 = dpi;
}
return dpi;
}打家劫舍III
leetcode337 --- 打家劫舍III【中等题】 题目描述
题目描述
在这道题中，我们将数组换为了二叉树，我们需要进行隔层“偷窃”。
1、解题思路
在这道题中，我们依旧是使用动态规划进行处理。我们再次来分析动态规划的三个要素：
- 动态数组的状态定义：分析题目可以知道，我们需要记录的每个节点的最大值，所以我们的状态数组
dp需要记录两个信息，一个是当前的节点，另一个是当前小偷到达当前节点时，能够获得的最大的金额。所以我们可以使用一个map来进行存储。 - 状态转移方程：由于我们使用的是二叉树，在二叉树中，我们只能不断的向下进行遍历，无法获取前期的状态，即：我们无法得知
dp[i-2]和dp[i-1]的状态，因此我们需要换一种思维，从后向前进行遍历，即：dp[i] = max(dp[i+2] + nums[i] , dp[i+1])。所以状态返程为：- 当前节点选择偷取，则当前节点的值为：
cur = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right) - 如果不选择当前节点，则应该交给下一层节点进行调用：
cur = rob(root.left) + rob(root.right)
- 当前节点选择偷取，则当前节点的值为：
- 基本状态：当我们遍历到空节点的时候，返回一个0值即可。
2、代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//动态规划中的备忘录
HashMap<TreeNode, Integer> memo = new HashMap<>();
public int rob(TreeNode root) {
if(root == null) return 0;
//判断当前的root是否已经计算过了
if(memo.containsKey(root)){
return memo.get(root);
}
//选择当前节点
int cur = root.val;
if(root.left != null){//下一次的选择将会到达下一层
cur += rob(root.left.left) + rob(root.left.right);
}
if(root.right != null){//下一次的选择将会到达下一层
cur += rob(root.right.left) + rob(root.right.right);
}
//不选择当前节点
int next = rob(root.left) + rob(root.right);
int res = Math.max(cur,next);
//存入备忘录中
memo.put(root,res);
return res;
}
}