动态规划之打家劫舍系列

前言

打家劫舍问题是一种非常经典的有限制条件的动态规划问题，按理说，不是一种特殊的类型，但是因为力扣上纯纯的出了三道题（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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

题目2： 213. 打家劫舍 II

题目描述：

相比于第一题，第二题加了限制条件，房子围成了一个圈，那么第一个房子是否抢直接影响到最后一个房子是否能抢（这里其实不能直接论第一个房子是否能抢，因为他要受第二个房子的限制，这里应该理解成第一个房子是否能在被抢的范围内，如果在，那么最后一个房子肯定不在被抢的范围内，如果不在，那么最后一个房子应该在被抢的范围内，因为它可能会让整个抢劫的值最大）
那么根据以上分析，分为两种情况，考虑范围分别为:(0,n-1)与(1,n)

解法

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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

题目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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44