代码随想录 (programmercarl.com)
1.确定dp数组以及下标的含义
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[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] 推导出来的，那么一定是从前到后遍历
class Solution {
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 + 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 - 2] + nums[i], dp[i - 1]);
}
return dp[nums.length - 1];
}
}需要提前将其他特殊情况考虑到，比如数组长度为0或1的情况。
一个数组成环之后，需要考虑三种情况：
情况一：考虑不包含首尾元素
情况二：考虑不包含尾元素
情况三：考虑不包含首元素
此处注意是【考虑】，不是一定要“偷”，情况二和情况三是包含情况一的，所以只需要考虑情况二和情况三即可。
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if (nums == null | len == 0){
return 0;
}
if (len == 1){
return nums[0];
}
return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
}
int robAction(int[] nums, int start, int end){//打家劫舍的逻辑
int pre = 0, cur = 0, tmp;
for(int i = start; i < end; i++){
tmp = cur;
cur = Math.max(pre + nums[i], cur);
pre = tmp;
}
return cur;
}
}注意：代码中pre的取值是关键，确保不会“偷”到相邻的房屋！
树形dp问题入门===递归三部曲+动规五部曲
1.确定递归函数的参数和返回值
确定dp数组以及下标的含义
偷dp[0]与不偷dp[1]这个节点
dp[i]：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
所以本题dp数组就是一个长度为2的数组
2.确定终止条件
在遍历的过程中，如果遇到空节点的话，无论偷还是不偷都是0，所以就返回。
相当于dp数组的初始化。
3.遍历顺序
后序遍历（左右中），?因为要通过递归函数的返回值来做下一步计算。
4.确定单层递归的逻辑（中）
如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0];?
如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
dp[0],dp[1]对应于va2,val1，前者不偷，后者偷。
/**
* 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 {
public int rob(TreeNode root) {
int[] res = robAction(root);
return Math.max(res[0], res[1]);
}
int[] robAction(TreeNode root){
int[] res = new int[2];
if (root == null){//递归终止条件
return res;//返回初始化的[0,0]
}
//后序遍历：左-右-中
int[] left = robAction(root.left);//左
int[] right = robAction(root.right);//右
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);//不偷根节点
res[1] = root.val + left[0] + right[0];//偷根节点，不偷左右孩子
return res;
}
}