打家劫舍是dp解决的经典问题

198.打家劫舍

文章链接：代码随想录 (programmercarl.com)

思路：自己的思路是，将数组重新划分为两个数组，分别对两个数组进行01背包计算最大收益，然后比较两个收益，取两者中的最大值

看完文章后的反思：前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。所以这里就更感觉到，当前状态和前面状态会有一种依赖关系，那么这种依赖关系都是动规的递推公式。

递归五部曲：

（1）确定dp数组（dp table）以及下标的含义

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

（2）确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是容易混淆的点）

然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

（3）dp数组如何初始化

从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]

从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

（4）确定遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

Java代码：

class Solution {public int rob(int[] nums) {//先判断特殊情况if(nums.length == 0 || nums == null){return 0;}if(nums.length == 1){return nums[0];}//动规五部曲//(1)确定dp数组的含义,dp[i]表示从0到i(包括i)个房屋所能偷取到的最大金额//(2)确定递推公式,dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]);//(3)初始化,dp[0] = nums[0],dp[1] = Math.max(nums[0],nums[1]);//(4)确定遍历顺序,从前往后int[] dp = new int[nums.length];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 - 2] + nums[i],dp[i - 1]);}return dp[nums.length - 1];}
}

213.打家劫舍||

文章链接：代码随想录 (programmercarl.com)

思路：与198不同，此时变成了环，意味着首尾相连，自己的思路是，重新定义一个数组，长度+1，将首位置的值放入到末尾的后面

看完文章后的思路：

该题其实可以考虑两种情况，（1）不考虑首，即从数组1位置到最后（2）不考虑尾，即从数组0位置到nums.length - 1位置

将循环拆成两列这个思路记在脑子里，以后再看到类似的多了种思路。

学习到的知识：

（1）Arrays.copyOfRange方法：主要用于对一个已有的数组进行截取复制，复制出一个左闭右开区间的数组。

Java代码：

class Solution {public int rob(int[] nums) {if (nums.length == 1) return nums[0];return Math.max(help(Arrays.copyOfRange(nums, 0, nums.length - 1)),help(Arrays.copyOfRange(nums, 1, nums.length)));}public int help(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];dp[1] = nums[0];for (int i = 2; i <= n; i++)dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);return dp[n];}
}

337.打家劫舍|||（树形DP入门题）

文章链接：代码随想录 (programmercarl.com)

思路：所谓树形DP就是在树上进行递归公式的推导。

递归三部曲+动规五部曲

Java代码：（注意看注释）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {// 不偷：Max(左孩子不偷，左孩子偷) + Max(又孩子不偷，左孩子偷)// root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +// Math.max(rob(root.right)[0], rob(root.right)[1])// 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷// root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;public int rob(TreeNode root) {return Math.max(help(root)[0],help(root)[1]);}//递归三部曲，(1)确定函数的返回值和参数private int[] help(TreeNode root){//动规五部曲//1.确定dp数组含义,表示//下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。//2.确定递推公式,如果不偷该节点，就在左右孩子中选择各自的最大值，再相加//如果偷该节点，那么就不偷左右孩子，只偷该节点//3.初始化，遇到空节点，均为0int[] dp = new int[2];//(2)确定终止条件(动规的3.)if(root == null){return dp;}//(3)确定单层递归逻辑，使用后序遍历，左右中int[] left = help(root.left);int[] right = help(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;}
}