创意DP点如何快速落地？-查作网

“创意DP点”是一个非常棒的概念，它指的是在动态规划中，那些不常见、非常规、但一旦想到就能让问题豁然开朗的“题眼”或“突破口”。

创意DP点如何快速落地？-图1

常规的DP通常是线性或网格状的（如 dp[i] 或 dp[i][j]），而创意DP点则是在状态定义上的奇思妙想，下面我将从核心思想、经典案例、解题步骤三个方面，为你系统性地梳理和解析这些“创意点”。

核心思想：打破常规，重新定义“状态”

创意DP的本质，是跳出“dp[i] 表示前 i 个元素”的思维定式，它要求我们深入问题本质,思考：

什么才是真正需要记录的“历史信息”？
如何用最精简的状态，来描述一个复杂的情况？

下面我们通过经典案例来感受这些“创意点”的威力。

创意DP点分类与经典案例

我将创意DP点分为以下几类,每类都有代表性的问题。

状态压缩 DP

核心思想：当状态中包含多个独立的、且每个状态只有有限种取值（通常是“是/否”、“0/1”）的元素时，我们可以用一个整数（二进制位）来表示这一组状态。
适用场景：状态由多个布尔型或小型离散值组成。
案例1：棋盘问题（如 N-Queens, N-Kings）
- 问题：在 N x N 的棋盘上放置 N 个皇后,使得它们互不攻击。
- 常规思路：DFS + 回溯,效率不高。
- 创意DP点：
  - 我们按行放置皇后，定义 dp[row][col_mask][diag_mask][anti_diag_mask] 为“处理到第 row 行，当前列的占用情况、主对角线占用情况、副对角线占用情况”下的方案数。
  - col_mask, diag_mask, anti_diag_mask 就是一个个状态压缩的整数，第 i 位为 1 表示第 i 列（或对角线）被占用。
  - 状态定义：dp[row][mask]，mask 可以同时编码列、主副对角线的占用情况。
- 效果：将一个二维棋盘问题，转化为了一个在“状态空间”中按行遍历的线性DP问题。
案例2：旅行商问题
- 问题：有一个旅行商要访问 n 个城市,求一条访问所有城市并回到起点的最短路径。
- 常规思路：全排列，时间复杂度 O(n!),不可行。
- 创意DP点：
  - 定义 dp[mask][u] 为“已经访问过的城市集合为 mask（一个二进制数），当前位于城市 u”时,已经走过的最短路径长度。
  - mask 是一个状态压缩。mask = 1011 (二进制) 表示已经访问了城市 0, 1, 3。
  - 状态转移：dp[mask][u] = min(dp[mask_without_v][v] + dist[v][u])，v 是 mask 中包含的城市，且 v != u。
- 效果：将指数级的复杂度降低到了 O(n^2 * 2^n)，对于 n=20 左右的问题可以接受。

轮廓线 DP

核心思想：在处理二维网格（如方格、棋盘）时，我们不按“行”或“列”为单位，而是按“格”为单位，状态需要记录当前格子及其“轮廓线”上方的信息，以确保后续决策的合法性,轮廓线通常指从左上到当前点的一条斜线。
适用场景：网格上的放置、覆盖、连通性问题，特别是需要处理“连通性”或“形状”时。
案例：骨牌覆盖问题
- 问题：用 1x2 的骨牌覆盖 2xN 的棋盘,有多少种覆盖方法？
- 常规思路：dp[i] 表示前 i 列的覆盖方法，dp[i] = dp[i-1] + dp[i-2]，这是一个斐波那契数列,太简单。
- 进阶问题：用 L 型骨牌覆盖一个有缺口的 2xN 棋盘。
- 创意DP点：
  - 我们按格遍历，定义 dp[i][j][state] 为“处理到第 i 行，第 j 列，且当前轮廓线上方的形状状态为 state”时的方案数。
  - state 是一个关键，它描述了从上一行“伸”下来的未覆盖的格子形状。state 可以是 0（无）、1（左边有缺口）、2（右边有缺口）等。
  - 状态转移：根据当前格子和 state，决定如何放置骨牌。state 表明上一行有缺口,当前格子必须与之连接。
- 效果：完美解决了形状和连通性带来的“历史依赖”问题,是处理复杂网格问题的利器。

序列上的状态机/有限状态自动机

核心思想：将问题抽象成一个有限状态机，DP状态表示“处理到序列第 i 个元素时，处于某个特定状态”。
适用场景：字符串匹配、股票买卖、股票交易冷却期等，问题本身就有明确的“阶段”和“规则”。
案例1：股票交易问题系列
- 问题：可以进行多次交易，但卖出后第二天不能买入（冷冻期）。
- 创意DP点：
  - 我们不记录“钱”，而是记录“当前处于什么状态”。
  - 定义 dp[i][j]，j 代表状态：
    - j = 0: 持有股票
    - j = 1: 不持有股票，且处于冷冻期（即今天刚卖出）
    - j = 2: 不持有股票，且不处于冷冻期
  - 状态转移：
    - dp[i][0] 可以从 dp[i-1][0] (继续持有) 或 dp[i-1][2] (今天买入) 转移而来。
    - dp[i][1] 只能从 dp[i-1][0] (今天卖出) 转移而来。
    - dp[i][2] 可以从 dp[i-1][1] (冷冻期结束) 或 dp[i-1][2] (继续保持) 转移而来。
- 效果：将复杂的交易规则，清晰地映射到了状态转移图上,逻辑一目了然。

树形 DP

核心思想：将DP应用到树或图的结构上，状态定义通常以“以某个节点为根的子树”为单位，并通过“后序遍历”的方式,在子树信息的基础上求解父节点问题。
适用场景：树上的选/不选问题、路径问题、独立集问题等。
案例：树上的最大独立集
- 问题：在树中选择一个节点集合，使得任意两个节点不相邻,且节点数最多。
- 创意DP点：
  - 定义 dp[u][0] 表示“在以 u 为根的子树中，不选节点 u 时的最大独立集大小”。
  - 定义 dp[u][1] 表示“在以 u 为根的子树中，选节点 u 时的最大独立集大小”。
  - 状态转移：
    - dp[u][1]：如果选了 u，那么它的所有子节点都不能选。dp[u][1] = 1 + Σ(dp[v][0])，v 是 u 的子节点。
    - dp[u][0]：如果不选 u，那么它的子节点可以选也可以不选，取最大值。dp[u][0] = Σ(max(dp[v][0], dp[v][1]))。
- 效果：将一个全局的图论问题，通过树形结构,巧妙地分解成了局部的子问题。

双序列/区间 DP

核心思想：状态由两个维度定义,通常表示两个子序列的匹配情况或一个区间的处理情况。
适用场景：字符串编辑距离、

创意DP点如何快速落地？

核心思想：打破常规，重新定义“状态”