打家劫舍

可以体会一下, 当前房屋偷不偷取决于前一个房屋和前两个房屋是否被偷了, 所以这种依赖关系就是dp的递推公式

1. dp[i]: 考虑下标i以内的房屋, 最多可以偷窃的金额为dp[i]
2. 递推公式: 决定的因素就是第i房间是偷还是不偷, 然后比较max
   1. 偷i的话, 那么dp[i] = dp[i-2] + nums[i] (不会偷上一个, 然后加上i)
   2. 不偷i的话, 那么dp[i] = dp[i - 1]
3. 初始化: 可以从递推公式看出, 基础就是dp[0]和dp[1], 从定义可以看出dp[0]一定是nums[0], dp[1]一定是nums[0]和nums[1]的最大值(0-最多偷窃的金额为nums[0]; 1-只有两间房, 偷金额大的那个)
4. 遍历顺序: 从前到后
5. 最后dp数组的最后一个值就是结果, 所以其实是length-1的位置

class Solution {public int rob(int[] nums) {//前面要多剪剪枝if(nums.length == 0 || nums == null){return 0;}if(nums.length == 1){return nums[0];}//开始dp数组创建和初始化int[] dp = new int[nums.length + 1];dp[0] = nums[0];dp[1] = Math.max(nums[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];}
}

打家劫舍II

唯一的区别就是变成环了

成环主要考虑三种情况:

1. 考虑不包含首尾元素
2. 考虑包含首元素, 不包含尾元素
3. 考虑包含尾元素, 不包含首元素

(而其实情况二和三已经包含了情况一, 所以比较二三就行了)

可以先看一下完整版代码: 注意关于start和end的变量设置

class Solution {public int rob(int[] nums) {//还是一样的剪枝int len = nums.length;if(nums == null || len == 0){return 0;}if(len == 1){return nums[0];}//开始判断两种条件//首先是只考虑头int result1 = robRange(nums, 0, len - 2);//然后是只考虑尾int result2 = robRange(nums, 1, len - 1);return Math.max(result1, result2);}public int robRange(int[] nums, int start, int end){//这里还要判断一下, 两个数相等, 就去第一个, 否则后面的max会出错if(end == start) return nums[start];//这里还是打家劫舍逻辑int[] dp = new int[nums.length + 1];dp[start] = nums[start];dp[start + 1] = Math.max(nums[start], nums[start + 1]);for(int i = start + 2; i <=end; i++){dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[end];}
}

简化版: 动态方程就是1. 偷了n(dp[n + 1]就是dp[n]) 2. 没偷n(dp[n + 1]就是dp[n-1] + num)

这里的思想就是用n+1的位置

class Solution {public int rob(int[] nums) {int len = nums.length;if(len == 0 || nums == null){return 0;}if(len == 1){return nums[0];}int result1 = robHelper(nums, 0, len - 1);int result2 = robHelper(nums, 1, len);return Math.max(result1, result2);}public int robHelper(int[] nums, int start, int end){if(start == end) return nums[start];int pre = 0, cur = 0, temp = 0;//利用滚动数组来模拟dpfor(int i = start; i < end; i++){temp = cur;cur = Math.max(pre + nums[i], cur);pre = temp;}return cur;}
}

打家劫舍III

这次就变成了二叉树

回想起之前的遍历方式, 这里是后序, 因为通过递归函数的返回值来做下一步计算

若抢了当前节点, 两个孩子就不能动, 如果没抢当前节点, 就可以考虑抢左右孩子

树形dp, 结合递归三部曲和动规五部曲

1. 确定返回值: 就是返回dp数组, 长度为2.下标为0记录不偷该节点所得到的最大金钱, 下标为1记录偷该节点所得到的最大金钱

2. 确定终止条件: 如果遇到空节点时, 偷或不偷都是0, 所以return

3. 遍历顺序: 使用后序

4. 单层递归的逻辑:

   1. 如果偷当前, 两个孩子就不能偷, cur.val + left[0] + right [0]
   2. 如果不偷, 就可以偷孩子 max(left[0], left[1]) + max(right[0], right[1])

   最终就是return(val2, val1), 不偷得到的最大钱和偷得到的

class Solution {public int rob(TreeNode root) {int[] res = robRecur(root);return Math.max(res[0], res[1]);}private int[] robRecur(TreeNode root){//穿件一个长度为2的数组int[] dp =  new int[2];//先确定终止条件if(root == null){return dp;}//后序遍历int[] left = robRecur(root.left);int[] right = robRecur(root.right);//单层逻辑//首先是不偷的情况, 那么就是偷孩子, dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);//然后是偷的情况, 所以孩子就不能偷dp[1] = root.val + left[0] + right[0];return dp;}
}