树状DP算法：树形图上的动态规划

# 2.1 树形图的定义和特性

树形图是一种无向无环图，它具有以下特性：

* **唯一根节点：**树形图中存在一个唯一的根节点，所有其他节点都与根节点相连。
* **无环：**树形图中不存在任何环路，即从一个节点出发，不能通过重复经过其他节点回到该节点。
* **连通：**树形图中所有节点都是连通的，即从任意一个节点出发，都可以通过一条路径到达其他任意节点。
* **层次结构：**树形图具有层次结构，根节点位于最顶层，其他节点按层级关系依次向下延伸。

# 2. 树状DP算法的基本原理

### 2.1 树形图的定义和特性

**树形图的定义：**

树形图是一种无向连通图，满足以下条件：

* 存在一个被称为根节点的特殊节点。
* 对于图中的任意两个节点，都存在一条唯一路径将它们连接起来。

**树形图的特性：**

* **无环：**树形图中不存在环路，即不存在从一个节点出发，经过若干条边后又回到该节点的路径。
* **层级结构：**树形图可以表示为一个层次结构，根节点位于最顶层，其他节点按层级依次排列。
* **子树：**树形图中，以某个节点为根节点的子图称为该节点的子树。
* **叶节点：**没有子节点的节点称为叶节点。

### 2.2 树状DP算法的思想和步骤

**树状DP算法的思想：**

树状DP算法是一种动态规划算法，利用树形图的层级结构和无环特性，将问题分解为多个子问题，逐层解决，最终得到整体问题的最优解。

**树状DP算法的步骤：**

1. **确定状态：**定义每个节点在不同状态下的状态值，例如节点的权重、路径长度等。
2. **确定转移方程：**根据树形图的结构和问题的要求，确定从父节点到子节点的状态转移方程。
3. **确定边界条件：**确定叶节点或根节点的初始状态值。
4. **自底向上或自顶向下：**自底向上或自顶向下地遍历树形图，根据转移方程更新每个节点的状态值。
5. **求解最优解：**根据根节点的状态值，得到整体问题的最优解。

**树状DP算法的优点：**

* **效率高：**利用树形图的层级结构，可以避免重复计算，提高算法效率。
* **易于理解：**算法思想简单，易于理解和实现。
* **通用性强：**可以解决多种树形图上的优化问题。

# 3. 树状DP算法的经典应用

### 3.1 最长公共子序列问题

**问题描述：**

给定两个长度分别为 m 和 n 的序列 A 和 B，求出 A 和 B 的最长公共子序列（LCS）。LCS 是 A 和 B 的一个子序列，并且是 A 和 B 的公共子序列中最长的。

**树状DP算法求解：**

树状DP算法求解 LCS 问题可以将问题转化为一个在树形图上求最长路径的问题。具体步骤如下：

1. **构造树形图：**将序列 A 和 B 的元素作为树形图的节点，对于 A 中的每个元素 a，在树形图中添加一个节点 a，对于 B 中的每个元素 b，在树形图中添加一个节点 b。然后，对于 A 中的每个元素 a，将与 a 相同的 B 中的元素 b 连接到 a。
2. **定义状态：**定义状态 f(i, j) 表示以 A 中第 i 个元素和 B 中第 j 个元素结尾的最长公共子序列的长度。
3. **状态转移方程：**状态转移方程为：
- f(i, j) = f(i-1, j) 如果 a[i] != b[j]
- f(i, j) = f(i-1, j-1) + 1 如果 a[i] = b[j]
4. **边界条件：**
- f(0, j) = 0
- f(i, 0) = 0
5. **计算顺序：**从左上角开始，逐行逐列计算状态 f(i, j)。
6. **结果：**最终，LCS 的长度为 f(m, n)。

**代码实现：**

def lcs(a, b):
    m, n = len(a), len(b)
    f = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                f[i][j] = f[i - 1][j - 1] + 1
            else:
                f[i][j] = max(f