前言

打家劫舍问题是一种非常经典的有限制条件的动态规划问题，按理说，不是一种特殊的类型，但是因为力扣上纯纯的出了三道题（1，2，3）来考察，题目的难度是依次递进的，还结合了一种不同的数据结构-二叉树，形成了一道二叉树中的动态规划问题，十分值得关注。

解决方案

打家劫舍是标准的动态规划问题，具备了动态规划需要具备的三个条件。
首先是状态的定义：dp[i]定义为：前i个房子所能偷到的最大金额
第一：最优子结构：小偷想要在偷完所有的(n)房子且不触发警报的情况下，偷得的金额最大，那么就要在前n-1个房子偷的金额最大，依次类推，在前n-2个房子也要最大
第二：状态转移方程：这里就要考虑限制条件，所以提出具体的题目进行分析。

打家劫舍基础

最重要的是我们对状态的定义，这道题状态的定义可以模仿最大子数组中状态的定义。
dp[i]定义为抢劫了前i家所能抢到的最大金额
至于为什么这样定义，因为这样定义才能让我们好写状态转移方程，如果说我们成以第i家为结尾（必须抢第i家）抢到的最大金额。
我们举个栗子:
对于数组:[1,8,3]，如果按第二种定义方法，dp[2]等于多少？
dp[0]=1;
dp[1]=8;
dp[2]=1+3=4;
明显的我们看到dp[2]应该等于8，但是由于我们状态的定义，我们必须取到nums[2]，所以就是不对的

题目1：198. 打家劫舍

解法

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];//状态定义很重要，不然很难弄，这里的状态dp[i]定义为前i个房子所抢的最高金额//状态这样定义后就不用纠结dp[0]到底该赋值什么，不要把它和后面联系起来，现在就看//第0个之前的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];}
}

题目2： 213. 打家劫舍 II

解法

class Solution {public int rob(int[] nums) {if(nums==null || nums.length==0){return 0;}if(nums.length==1){return nums[0];}if(nums.length==2){return Math.max(nums[0],nums[1]);}if(nums.length==3){return Math.max(Math.max(nums[0],nums[1]),nums[2]);}return Math.max(robapart(0,nums.length-1,nums),robapart(1,nums.length,nums));}public int robapart(int begin,int end,int []nums){int []dp=new int[nums.length-1];dp[0]=nums[begin];dp[1]=Math.max(nums[begin],nums[begin+1]);for(int i=2;i<nums.length-1;i++){dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i+begin]);}return dp[nums.length-2];}
}

题目3：337. 打家劫舍 III

/*** 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 {Map<TreeNode,Integer>memo=new HashMap<>();public int rob(TreeNode root) {//今天学习一种新的做法//我们最少需要几个元素进行递归的考虑，就选择最少的元素//然后进行其中代码的撰写，考虑每个元素做什么就好if(root==null){return 0;}if(memo.containsKey(root)){return memo.get(root);}int sum1=root.val;if(root.left!=null){sum1+=rob(root.left.left)+rob(root.left.right);}if(root.right!=null){sum1+=rob(root.right.left)+rob(root.right.right);}int sum2=rob(root.left)+rob(root.right);int res=Math.max(sum1,sum2);memo.put(root, res);return res;}
}