「动态规划」简单多状态dp问题

以经典问题“打家劫舍”来解释简单多状态dp问题和解决方法

打家劫舍I

题目链接：打家劫舍I

这种问题就是在某一个位置有多个状态可以选择，选择不同的状态会影响最终结果
在这道题中就是小偷在每一个房屋，可以选择偷或不偷，每一次选择都会影响最终偷窃金额

1. 状态表示
   因为每一步都有两个状态，所以我们要用两张dp表来表示，分别记为 f 和 g，f[i]表示从开始到第 i 号房屋，偷窃第 i 号房屋可获得的最大金额；g[i[则表示不偷第 i 号房屋可获得的最大金额
2. 状态转移方程
   推导转移方程常用的策略就是找最近的一步，离f[i]最近的一步就是 i - 1，而偷了第 i 号房屋就意味着第 i - 1 号不能偷，也就是 g[i-1] + nums[i]
   而对于g[i]，因为在此状态下第 i - 1 号房间可偷可不偷，也就是对应f[i-1] 和 g[i-1]，我们要的是最大金额，所以取它们两者中的较大值即可，即g[i] = Math.max(f[i - 1],g[i - 1])
3. 初始化
   状态转移方程涉及了 i - 1，所以我们要初始化 f[0] 和 g[0]，显然f[0]初始化为nums[0]就ok了，g[0]初始化为0
4. 填表顺序
   从左往右填
5. 返回值
   比较 f 和 g 最后一个元素，谁大就返回谁

代码如下：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0]; g[0] = 0;
        for(int i = 1;i < n;i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[n-1],g[n-1]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

当然，我们要讲的肯定不止一道题，上面的题只是基础题。而当我们面对中等题、难题时，要有能力将它们转化为我们见过的题，下面以两道题示例：

打家劫舍II

题目链接：打家劫舍II

在这道题中，房屋的排列变成了环形
如果偷第1个房屋，那就不能偷第二个和最后一个，此时第三个房屋到最后一个房屋其实是直线形，那就可以用打家劫舍I的思路来解决
如果不偷第一个房屋，那么第二个房屋到最后一个房屋也是直线形，也可以参考上面的思路
通过讨论不同的情况，我们都可以把环形的问题转化为之前解决过的直线形的问题

那接下来只需对两种情况分别使用打家劫舍I的思路，然后返回最大值即可，因为代码会涉及到相同的的部分，所以我们封装为一个函数

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(rob1(nums,2,n-2)+nums[0],rob1(nums,1,n-1));
    }

    public int rob1(int[] nums,int left,int right) {  //对[left,right]区间进行“打家劫舍”
        if(left > right) return 0;
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[left] = nums[left];
        for(int i = left+1;i <= right;i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[right],g[right]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

删除并获得点数

这道题意思就是说选了一个点数之后，不能再选大小和它相邻的点数，因为数组中可能会有多个相同的点数，所以我们先把相同的点数求和，放进一个新的数组（新数组和每个点数之间存在映射关系，比如点数1就放在该数组下标为1的位置），然后我们可以对新数组采用打家劫舍

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int max = 0;
        int[] sum = new int[10001];  //记录nums中每个数字出现的总和
        for(int i = 0;i < n;i++)
            sum[nums[i]] += nums[i];

        //对sum进行打家劫舍
        return rob(sum);
    }

    public int rob(int[] sum) {
        int n = sum.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[1] = sum[1];
        for(int i = 2;i < n;i++) {
            f[i] = g[i-1] + sum[i];
            g[i] = Math.max(g[i-1],f[i-1]);
        }
        return Math.max(f[n-1],g[n-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