背景

AtCoder DP Contest 的 C 题，开始感受到 DP 的”状态转移”了——不仅要记录最优值，还要记录当前选了哪个活动。

题目描述

每天有 3 种活动可以选择（0、1、2），每种活动获得不同的快乐值。要求相邻两天不能选相同的活动，求 N 天能获得的最大总快乐值。

思路分析

定义 dp[i][j] 为第 i 天选活动 j 时的最大总快乐值。

当天选了活动 0，就枚举前一天选 1 或 2 的最大值，加上今天的快乐值，其他同理。

1
2
3
dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i][0]
dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + a[i][1]
dp[i][2] = max(dp[i-1][1], dp[i-1][0]) + a[i][2]

最后在 dp[n][0]、dp[n][1]、dp[n][2] 中取最大值。

这个思路是把”不能连续相同”转化为”枚举上一步的两种可能性”，是 DP 状态设计的典型手法。

代码实现

1
2
3
4
5
6
for (int i = 1; i <= n; i++) {
    dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][2]) + a[i][0];
    dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][2]) + a[i][1];
    dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][0]) + a[i][2];
}
System.out.println(Math.max(dp[n][0], Math.max(dp[n][1], dp[n][2])));

小结

  • DP 的状态定义决定了转移方式，这题每个状态只跟前一个状态有关，是线性 DP
  • 约束”相邻不能相同”转换为”枚举排除当前选项后的最大值”，这个思路在其他类似问题中很常见