算法合集：动态规划（二）——状态dp

一、线性状态dp

线性状态dp也是线性dp的一种，但稍复杂一点。他们的本质区别在：线性dp只需要考虑一个状态的递推，状态dp需要考虑多个变量之间的动态递推。
但也因为状态多了，其实难度反而降低了
在例题中会讲到状态dp的无敌模板

1、状态dp例题以及解题模板

1）例题一：LeetCode 198 打家劫舍
与线性dp不同的是，状态dp中有多个维度，也就是每个房子既有可能被偷，也有可能不被偷，两种情况都要考虑，换句话说，无论前面一次递推结果如何，后一次都要考虑两种情况

状态dp的无敌模板：增加维度
将dp数组从一维变成二维dp[i][j]
其中第二维的j只能取0或1，用来表示当前的房子是否被偷
dp[i][0]表示第i栋房子没被偷，dp[i][1]表示第i栋房子被偷了
所以我们每次都要维护同一房子的两个变量，对应的动态转移方程也有两个

• 如果选择不偷当前的第i栋房子，那么第i - 1栋房子可以被偷，也有可能没被偷
• dp[i][0] = max(dp[i - 1][1], dp[i - 1][0])
• 如果选择偷当前的第i栋房子，那么第i - 1栋房子一定不能被偷过
• dp[i][1] = dp[i - 1][0] + price[i]

接下来注意一下初始化就好

• dp[0][0]也就是不偷最开始的房子dp[0][0] = 0
• dp[0][1]也就是偷最开始的房子dp[0][1] = price[0]

public int rob(int[] nums) {
    int[][] dp = new int[nums.length][2];
    dp[0][1] = nums[0];
    dp[0][0] = 0;
    for (int i = 1; i < nums.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + nums[i];
    }
    return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
}
1
2
3
4
5
6
7
8
9
10

当然可以进行优化，每个房子的状态用两个int来表示即可

public int rob(int[] nums) {
    int rob = nums[0]; // 偷
    int pass = 0; // 不偷
    for (int i = 1; i < nums.length; i++) {
        int pre_pass = pass; // 计算rob时用的是上一次的pass
        pass = Math.max(pass, rob);
        rob = pre_pass + nums[i];
    }
    return Math.max(pass, rob);
}
1
2
3
4
5
6
7
8
9
10

2）例题二：LeetCode 188 买卖股票的最佳时机Ⅳ
乍一看挺难，其实也是增加维度的思想

状态dp的无敌模板：增加维度
将dp数组变成三维dp[i][j][k]
其中第二维的j只能取0或1，表示手上是否持有股票
dp[i][0][k]表示第i天时手上没持有股票，dp[i][1][k]表示第i天时手上持有股票
第三维的k能取0 ~ k，dp[i][j][k]表示第i天时已经完成了k笔交易

然后便是动态转移方程

• 若第i天结束时手上没持有股票
• 则要么前一天结束时也没持有，要么今天卖出了股票并完成了一笔交易
• dp[i][0][k] = max(dp[i - 1][0][k], dp[i - 1][1][k - 1] + price[i])
• 若第i天结束时手上持有股票
• 则要么前一天结束时也持有股票，要么今天买入了股票
• dp[i][1][k] = max(dp[i - 1][1][k], dp[i - 1][0][k] - price[i])

最后是初始化

• dp[0][0][k] = 0，dp[0][1][k] = -price[0]其中k取0 ~ k

for (int i = 0; i <= k; i++) {
	dp[0][1][i] = -prices[0];
	dp[0][0][i] = 0;
}
1
2
3
4

为什么需要对第三维所有的dp[0][0]和dp[0][1]都赋值？
我们知道最多进行k笔交易
但并非是将k笔交易全部都进行完就一定是最佳答案，有可能天数不足以支持那么多笔交易
所以第三维度用来限定交易次数，最多k次，最少0次
答案就会在最后一天的所有限定的交易次数中产生

int ans = 0;
for (int i = 0; i <= k; i++)
	ans = Math.max(ans, dp[len - 1][0][i]);
return ans;
1
2
3
4

完整代码

public int maxProfit(int k, int[] prices) {
    int len = prices.length;
    if (len == 0) return 0;
    int[][][] dp = new int[len][2][k + 1];
    for (int i = 0; i <= k; i++) {
		dp[0][1][i] = -prices[0];
		dp[0][0][i] = 0;
	}
    for (int i = 1; i < len; i++) {
        dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][0][0] - prices[i]);
        for (int j = 1; j <= k; j++) {
            dp[i][0][j] = Math.max(dp[i - 1][0][j], dp[i - 1][1][j - 1] + prices[i]);
            dp[i][1][j] = Math.max(dp[i - 1][1][j], dp[i - 1][0][j] - prices[i]);
        }
    }
    int ans = 0;
    for (int i = 0; i <= k; i++)
        ans = Math.max(ans, dp[len - 1][0][i]);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

当然也是能优化的

public int maxProfit(int k, int[] prices) {
    if (k == 0 || prices.length == 0)
        return 0;
    int[] buy = new int[k + 1];
    int[] sell = new int[k + 1];

    // 初始化
    for (int i = 0; i <= k; i++) 
        buy[i] = -prices[0];
    sell[0] = 0;

    for (int i = 1; i < prices.length; i++)
        for (int j = 0; j <= k; j++) {
            // 未持有，前一天未持有 或 今天卖出，完成一次交易
            if (j > 0)
                sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);
            // 持有，前一天持有 或 今天买入
            buy[j] = Math.max(buy[j], sell[j] - prices[i]);
        }
    int ans = 0;
    for (int i = 0; i <= k; i++)
        ans = Math.max(ans, sell[i]);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2、实战题目

LeetCode 123 买卖股票的最佳时机Ⅲ
LeetCode 309 最佳买卖股票时机含冷冻期
LeetCode 714 买卖股票的最佳时机含手续费
最后思考一下：既限制k笔交易，又有冷冻期，还有手续费，并要求优化，怎么解？

二、环形状态dp

例题兼实战题：LeetCode 213 打家劫舍Ⅱ
由于房子是个环形，所以放弃第一家，和放弃最后一家都会对递推产生影响。
那么环形问题，可以转化成两次线性dp

• 第一次线性dp：不考虑最后一家。
• 第二次线性dp：不考虑第一家。

本题的递推方程在本篇文章的第一题已经讲解

• dp[i][0] = max(dp[i - 1][1], dp[i - 1][0])
• dp[i][1] = dp[i - 1][0] + price[i]

但本题最要注意的是，房子的数量最小为1，所以为了不失一般性，在递推时稍作改变

• 第一次线性dp：不考虑最后一家。为了一般性，我们递推到最后一家，但只取dp[i][0]
• 第二次线性dp：不考虑第一家。为了一般性，我们将dp[0][1]初始化为无穷小，使得即使偷了第一家，也会因为无穷小而舍弃掉这种选择

public int rob(int[] nums) {
    int len = nums.length;
    int[][] dp = new int[len][2];
    // 可以偷第一家，忽略最后一家
    int first= dp[0][1] = nums[0];
    for (int i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + nums[i];
    }
    first = Math.max(ans, dp[len - 1][0]);
    // 可以偷最后一家，不能偷第一家
    dp[0][0] = 0;
    dp[0][1] = -(int)1e9;
    for (int i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + nums[i];
    }
    return Math.max(first, Math.max(dp[len - 1][0], dp[len - 1][1]));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三、树形状态dp

例题兼实战题：LeetCode 337 打家劫舍Ⅲ
思路和线性的是完全一样，只不过此时不能由数组来记录前一次的结果了，所以我们使用HashMap

• HashMap<TreeNode, int[]> dp，存的是某个结点的两种情况，偷与不偷
• 若用cur[j]来表示当前结点的被偷情况
• cur[0]表示当前房子没被偷：由其左右儿子的被偷与没被偷情况组成，对应伪代码如下：
• cur[0] = max(leftNode.cur[0], leftNode.cur[1]) + max(rightNode.cur[0], rightNode.cur[1])
• cur[1]表示当前的房子被偷了：则其左右儿子均没被偷，对应伪代码如下：
• cur[1] = leftNode.cur[0] + rightNode.cur[0] + curNode.val

HashMap<TreeNode, int[]> dp = new HashMap<>();
public int rob(TreeNode root) {
    int[] cur = new int[2];
    if (root.left != null) {
        cur[0] += rob(root.left); // 偷左节点
        cur[1] += dp.get(root.left)[0]; // 不偷左节点
    }
    if (root.right != null) {
        cur[0] += rob(root.right); // 偷右节点
        cur[1] += dp.get(root.right)[0]; // 不偷右节点 
    }
    cur[1] += root.val;
    dp.put(root, cur);
    return Math.max(cur[0], cur[1]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15