力扣刷题笔记 #05-3 复杂动态规划

本文包含「动态规划」类型题中的：树形 DP、区间 DP、状压 DP、数位 DP 等。持续更新中。

题目描述：

方法1：

方法2：

方法3：

坑点：

动态规划（DP）适用于满足重叠子问题 + 最优子结构的问题，常用的方法有「记忆化搜索」、「递推」等。DP 的时间复杂度通常是「状态总数 \(\times\) 每个状态向其他状态转移的次数」。

动态规划（DP）的一般步骤：

1. 列出题目给的整体规模变量，例如 \(n,m\)
2. 用局部变量 \(i,j,k\) 描述一般状态，例如 \(dp[i][j]\)
3. 观察上述一般状态的最后一步，例如判断 \(s[i]==s[j]\)
4. 去掉最后一步，问题规模缩小，变成子问题，例如 \(dp[i-1][j-1]\)
5. 得到状态转移方程，例如 \(dp[i][j]=dp[i-1][j-1]+1\)
6. 初始值和最终状态，例如 \(dp[i][0]\)、\(dp[0][j]\) 和 \(dp[n][m]\)
7. 可选的转移优化，例如记忆化、前缀和等

树形 DP

树形 DP 的本质是「树上的一维线性 DP」，其约束和转移通常来自父节点或子节点（很少有跨层），常用的套路也是：线性递推和记忆化搜索。而区别在于，树上的操作必须依赖 DFS 进行：

• 线性递推：适用于每个节点只有一种状态且只由相邻节点转移时，此时无论是从「根到叶」还是「叶到根」，每个节点都只会被访问一次，因此可以直接 DFS。前者从根节点直接向下转移，后者需要到叶节点再回溯转移。
• 记忆化搜索：适用于每个节点有多个状态或可能受到祖先节点影响时，例如状态机 DP，此时需要的 vis 数组，可以通过哈希表映射存储每个节点对应的 DP 值，同时标记是否访问过。

337. 打家劫舍 III (M)

题目描述：同其他两题，但是房子排成二叉树形，除根节点外，每栋房子有且只有一个父房子与之相连。

方法1：树形 DP + 记忆化搜索，当前节点的值由子节点转移，从根节点往下 DFS。每个节点有两种操作，对应两种状态，用哈希表记录。时空复杂度均为 \(O(n)\)。

方法2：树形 DP + 递推，观察发现每个节点只受相邻节点影响，而且两个状态可以同时求出，利用一个 pair 捆绑作为 DFS 的返回值，无需哈希表。空间复杂度 \(O(1)\)。

LCP 64. 二叉树灯饰 (H)

题目描述：给定一个二叉树，树上每个节点均有一盏灯和三个开关，灯通过 \(0/1\) 表示关闭、开启状态。开关 1 切换当前灯；开关 2 切换当前点为子树的所有灯；开关 3 切换当前灯和左右子节点灯。计算最少操作几次可以关闭所有灯。

方法：树形 DP + 记忆化搜索，从根节点往下 DFS，每个节点会受到祖先节点、父节点选择的影响，变成开灯或关灯状态，而不同状态的当前节点，也会有不同操作使其最终关闭并且继续影响子节点。时间复杂度 \(O(n)\)。

定义状态 (当前节点原始状态亮/灭，祖先节点开关 2 的切换次数的奇偶性，父节点是否切换了开关 3)，每个状态表示从当前状态出发，最少需要操作多少次开关，可以关闭子树所有节点的灯。

如果 DFS 到当前节点时，其「原始状态 + 祖先节点 + 父节点」共同影响下为亮时，有四种操作：

• 操作开关 1；操作开关 2；操作开关 3；操作开关 123。
• 四种操作都能使灯最终为灭，且影响到子树，因此取最小值。

为灭时，也有四种操作：

• 不操作任何一个开关；操作开关 12；操作开关 13；操作开关 23。

坑点：每个节点虽然都是由其父节点转移，但是可能有四种转移方式，在递归深处的节点可能被反复计算了非常多次，因此需要记忆化。Python 中在函数前用 @cache 即可对函数的每次调用进行记忆化，如果是 C++ 则需要 vis 数组，对于树结构可以先用哈希表映射得到连续数组下标。

2831. 移除子树后的二叉树高度 (H)

题目描述：二叉树的中有 \(n<1e5\) 个节点，每个节点被分配 \(1\) 到 \(n\) 的不同值，给定 \(m<1e4\) 个查询，每次查询删除掉某个节点的所有子树后，整个树的高度（一个节点高度为 0）。

方法1：DFS 暴力，第一次 DFS 维护每个节点的 \(height\)，父节点及兄弟节点编号。每次查询时再自底向上回溯，先看有无兄弟，如果有兄弟再看兄弟的高度分类讨论。时间复杂度 \(O(nm)\)，超时。

方法2：两次 DFS + 树形 DP 线性递推，第一次 DFS 自底向上回溯算出 \(height\)，第二次 DFS 自顶向下算出 \(depth\)，同时在第二次 DFS 中，还可以自顶向下处理出答案，最后查询时直接取答案即可。时间复杂度 \(O(n)\)。

设删掉节点 root 的所有子树后的高度为 \(restH\)，则删掉其左子树的所有子树后整个树的高度有两种可能：

• 不包含 root 节点的路径最长：则这条节点贡献的高度就是 \(restH\)；
• 包含 root 节点的路径最长：则这条路径肯定来自 root 的右子树，因此就是此时 root 的 \(depth\) 加上右子树的 \(height\)。

其中 \(restH\) 只与父节点有关，因此可以自顶向下计算，这时一种 DP 的思想。

方法3：转 DFS 序 + 前缀处理，先 DFS 遍历并按顺序存下遍历过的节点编号（DFS 序），并预处理出每个节点的深度，并存储每个节点管辖的子树区间。每次删除点就相当于删除一段连续区间，并将原数组分为两段，分别代表子树的左侧和右侧。两端区间中每个节点深度的最大值即为答案，因此先预处理前缀和后缀 MAX，总时间复杂度 \(O(n)\)。

区间 DP

求解在一个区间上的最优解，可以将这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间。通常需要 \(O(n^3)\)，分别用三层循环来枚举：长度、起点、分割点。模板如下：

// 枚举长度，从小区间开始
for (int len = 1; len <= n; len++) { 
    // 枚举起点，ends <= n，区间为 [i, ends)
    for (int i = 0; i + len <= n; i++) { 
        int j = i + len;
        // 枚举分割点，更新当前区间最优解，注意 dp[i][i] = 0
        for (int k = i; k < j; j++) { 
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + something);
        }
    }
}

OJ 合并石子 (H)

题目描述一：N 堆石子排成一条线，要将石子有序的合并成一堆，每次可以合并任意的两堆，代价为一次合并的石子总数，求 N 堆石子合并成一堆的最小代价。

方法：贪心 + 优先队列，每次选择最小的两堆合并，合并后将新的结果放回队列，复杂度 \(O(n\log n)\)。本题实际上是求解哈夫曼树的变形。

题目描述二：同上，但每次只能合并相邻的两堆，求最小代价。

方法1：区间 DP，\(\text{dp}[i][j]\) 表示第 \(i\) 堆到第 \(j\) 堆石子合并的最小代价，\(\operatorname{sum}[i][j]\) 表示第 \(i\) 堆到第 \(j\) 堆石子的总数（前缀和），复杂度为 \(O(n^3)\)。状态转移方程如下： \[ \text{dp}[i][j]=\left\{\begin{array}{cc} 0 & i=j \\ \min \left(\text{dp}[i][k], \text{dp}[k+1][j] \right)+\text{sum}[i][j] & i \neq j \end{array}\right. \] 方法2：区间 DP + 四边形不等式优化（交叉小于包含），复杂度可优化为 \(O(n^2)\)。

题目描述三：同上，但是 N 堆石子排成环形！求最小代价。

方法1：区间 DP，采用 mod N 方式实现环形，但是要注意跨边界求解时前缀和、状态转移方程的书写。复杂度 \(O(n^3)\)。

方法2：区间 DP + 复制环，将原数组复制一遍扩展为 2N 长度，但此时最外层循环枚举最大长度仍为 N。复杂度 \(O(n^3)\)。

312. 戳气球 (H)

题目描述：\(n\) 个气球排成一排，每个气球上都标有一个数，存在数组 nums 中。扎破第 \(i\) 个气球，可以获得 nums[i-1] * nums[i] * nums[i+1] 枚硬币。求所能获得硬币的最大数量。

方法1：记忆化搜索，逆向思维，将整个过程看作每次添加一个气球直到填满，则 \(dfs(i,j)\) 表示将区间 \([i,j)\) 填满的答案，目标是 \(dfs(0, n)\)，每次需要枚举分割点并递归求解 \(dfs(i, mid)\) 和 \(dfs(mid+1, j)\)，采用记忆化防止重复搜索，状态数有 \(n^2\)，转移方向有 \(n\)，因此时间复杂度 \(O(n^3)\)，空间复杂度 \(O(n^2)\)。

方法2：区间 DP，正向思维，\(dp[i][j]\) 表示区间 \([i,j)\) 的答案，由于是半开半闭区间，起始时 \(dp[i][i]=0\)，目标是 \(dp[0][n]\)，依次枚举长度、起点、分割点，时间复杂度 \(O(n^3)\)，空间复杂度 \(O(n^2)\)。 \[ dp\left[ i \right] \left[ j \right] =\max \left( dp\left[ i \right] \left[ k \right] +dp\left[ k+1 \right] \left[ j \right] +nums\left[ i-1 \right] \times nums\left[ k \right] \times nums\left[ j \right] \right) \] 坑点：为了减少分类讨论，一开始可以对数组进行处理，在两边各加上 \(1\)，目标转化为 \(dfs(1, n+1)\) 和 \(dp[1][n+1]\)，防止下标越界。在 vector 起始位置插入元素采用 v.insert(v.begin(), 1)。

1000. 合并石头的最低成本 (H)

题目描述：

方法1：

方法2：

方法3：

状压 DP

也称为多维线性 DP，此类题的特点是数组很小，通常在 32 个数以内，可以将每一个元素用一个二进制位标记进行状态压缩，数组下标 0 的元素对应第 0 个二进制位，复杂度通常在指数级。

尽管数据范围很小，但在指数级复杂度下依然可能会溢出，如果直接用多维数组存储状态，匹配每个状态的时间要 \(O(\Sigma)\)，如果进行状态压缩，则只需要 \(O(1)\)，可以达到一个量级的优化效果。

状态压缩后的 DP 通常用一层循环递推求解，每个 dp[i] 可能转移到多个 dp[next]、也可能由多个 dp[before] 转移过来，其中 \(next\)、\(before\) 通过位运算求出。

698. 划分为 k 个相等的子集 (H)

题目描述：给定一个长度不超过 16 的整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，各子集的总和都相等。

方法1：暴力，如果元素总和不为 k 的倍数，失败；设有 k 个桶，每个元素都可能分进任何一个，复杂度 \(O(k^n)\)。

方法2：暴力 + 剪枝，先进行排序，优先使用剩余的最大数值搜索；依旧对每个元素判断是否可以进当前桶，如果无法放入，则搜索下一个桶；如果相邻两个桶内的总量相同，则第二个桶可以跳过。

方法3：状压 + DFS，用一个大小 1<<n 的 \(vis\) 数组表示状态，vis[s] 表示在数字 s 下是否可能成功，s 的二进制位为 1 代表该元素未被使用。共有 \(2^n\) 个状态，时间复杂度 \(O(2^n)\)。

初始将所有状态设为 true（表示所有状态都有可能），s 从全 1 开始 DFS（表示每个元素都未使用），递归结束的条件是 s 全 0（表示所有元素都被使用），直接返回 true。

DFS 前先将当前状态置 false，因为如果这个状态可能成功，那就必然直接成功；如果不能成功，则下次再访问到也只是顺序调换了，直接剪枝。

DFS 时，根据当前状态还有剩余 1 的个数进行分支（前提是加入该数后不会溢出），但是大部分分支不会访问到，实际访问不会超过 \(2^n\) 个状态。

方法4：状压 + DP，用一个大小 1<<n 的 \(dp\) 和 \(sum\) 数组表示状态及当前桶内总和，dp[s] 表示在状态 s 下是否可能成功，s 的二进制位为 0 代表该元素未被使用。递推求解，每个状态只会被求解一次，时间复杂度 \(O(2^n)\)。

初始将所有状态设为 false（表示所有状态都未知），只记 \(dp[0]=ture\)（表示每个元素都未使用时可能可行）。从 s 从全 0 开始递推，最终返回 dp[(1<<n)-1]。

DP 转移时，根据当前状态还有剩余 1 的个数进行转移得到 \(dp[next]\)，若加入该数后不会溢出，则该状态可能可行，标记为 true，否则保持 false。

DP 线性递推时，新来的每个 dp[i] 都会由比 i 小的若干状态转移过来，如果仍为 false，则表示不可能发生，直接剪枝。

1799. N 次操作后的最大分数和 (H)

题目描述：给定一个长度不超过 14 的整数数组，要求将其中数字两两配对，第 i 对可以获得 i*gcd(x,y) 积分，计算配对结束后能获得的最大分数和。

方法：状压 + DP，由于数据很少，先处理出 gcd 值。用大小 1<<n 的 \(dp\) 存储每个数被选中的状态，dp[s] 表示选中 s 时的分数和。顺序求解 \(2^n\) 个状态，每个状态有 \(n\) 种可能转移，且转移的来源必定求解过，复杂度 \(O(n\cdot 2^n)\)。

dp[s] = max(dp[s], dp[s ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);

用一层循环递推求 dp[s]，初始 dp[0]=0，返回 dp[(1<<n)-1]。由于每次的转移都是将两个 \(1\) 替换成 \(0\)，因此转移的来源必定求解过，所以直接访问 dp[s ^ (1 << i) ^ (1 << j)]。

数位 DP