模板索引：动态规划

一些感想

用了接近两周的时间把线性动态规划和区间环形动态规划过完了，对DP有了更加深刻的认识。
这里随性写一些杂想，主要是以后想找的时候不至于定位不到东西。

DP的精髓

DP的精髓在于用尽可能准确地状态和精简的转移，最大程度减少重叠子结构，并用一个中间状态表示尽可能多的最优子结构。

• 我们可以这样理解，绝大多数DP的思维都能从搜索转化而来，以洛谷P1854 花店橱窗布置这一题为例，为什么枚举花束的摆放进行搜索必爆而动态规划却可以轻松解决，明明他们表示的状态数应该是一样的啊：所有的花的摆法应该都会被遍历一遍以确保不会漏掉最优解法，那么动态规划到底比搜索快在哪里，我冥思苦想数日突然灵光一现：

  我们不妨先看看这题 P2363 马农 ，这题暴力枚举完的 \(O(n^6)\) 是无法通过的，但是我看到了一种很妙的解法：
  通过map映射区块值为 x 的方案数有多少种，成功把复杂度 \(O(n^6) \to O(n^4)\)，这种将两序列通过映射降低枚举握手 y 引入的 \(O(N^2)\) 复杂度思想很值得记忆。
  简单来说，你现在有两个长度为 \(n, m\) 的序列，全部互相枚举遍历复杂度是 \(O(nm)\)。 但是现在我采用桶排或者映射，能大幅降低枚举引入的复杂度。

  这两部分有什么共通性吗？这在于，在我们定义下的状态数量是没有改变的，但是我们状态之间的枚举、转移，是可以大大降低的。
  包括记忆化搜索、动态规划，降低复杂度的核心之一都在这里，我们的巧妙转移，我们的记忆化，都减少了状态之间的沟通握手成本。

• 另一个核心是，我们用一个中间状态表示尽可能多的最优子结构。
  以刚刚说的那题《花店橱窗布置》为例，暴力搜索的子问题（子结构）是有重叠的，只使用暴力搜索看似在搜索过程中无法剪枝与优化，但是在dp算法下，我们通过划分子问题使得一些重叠状态/子问题暴露出来从而简化：考虑现在有三盆花，在考虑加入第四盆花的时候，暴力搜索要把所有四种花的排列组合全部遍历一遍，最坏复杂度 \(n^4\)，而换用dp，可以认为第一第二种花的最优摆法在子任务已经实现过了，我们拆出这个问题，只考虑第四盆花接续在第三盆后面的情况即可，这种引入大大降低了复杂度，是一种更为厉害的分治子问题结构，而不是单纯的剪枝。例如在想这题 P1541 [NOIP 2010 提高组] 乌龟棋的时候我没想出来，在于设计状态思维固化了，使得状态与子问题重叠，自然会重复求解带来天量复杂度。
  我们可以这么认为，记忆化不只是做了搜索的子问题的记忆剪枝，避免重复遍历重叠子问题。更是把很多个子问题压缩最优解得到一个状态，这个状态表示很多子问题的最优解。
  怎么有一股量子计算的味道。。
  比如这题P4310 绝世好题。

• 还有一个问题在于我们经常思考出子问题重叠求解的设计，会使得局面扑朔迷离：
  比如我写P3146 [USACO16OPEN] 248 G这题时就设计出这样的状态：

int dp[maxn][maxn][4]; 
// dp[l][r][0] : 用完了整个区间
// dp[l][r][1] : 取了子序列的左边，不能使用右边
// dp[l][r][2] : 取了子序列的右边，不能使用左边
// dp[l][r][3] : 取[l,r]序列的中间，由左子序列的右边和右子序列的左边结合而来

实际上左右端点子序列和中间序列其实就包含在某个取完整序列的最优子结构中，完全不需要什么左子序列右子序列，只是此时应该使得在dp过程中不断取ans的max，只在结果取会因为两个不完整序列无法合并丢失子结构最优解。
同样的教训还有这题：P1220 关路灯（懒得打字了插个图）

谈谈区间dp

区间dp其实套路比较一般的貌似就两种转移：
一种是只能在一个区间的左边或者右边加入一个新的节点；（遍历端点，通常为 \(O(n ^ 2)\)）
一种是一个区间可以由区间内的子区间结合而来，这时要多枚举一个 \(k\) 来取出所有子序列的可能结合。(即还要讨论断点才能转移一个大区间，通常为 \(O(n ^ 3)\))

第一种情况如下，以P1435 [IOI 2000] 回文字串为例：

点击查看代码

cin >> s;
	len = s.length();
	for(int i = 0; i < len; i++) f[i][i] = 0; // 预处理边界条件子区间长为 1
	for(int i = 1; i < len; i++) // ；预处理边界条件子区间长为 2
		if(s[i] == s[i - 1]) f[i - 1][i] = 0; 
		else f[i - 1][i] = 1;
	
	for(int l = 2; l < len; l++)
	for(int i = 0; i+l < len; i++){
		int j = i + l;
		f[i][j] = min(f[i + 1][j] + 1, f[i][j - 1] + 1);
		if(s[i] == s[j]) f[i][j] = min(f[i + 1][j - 1], f[i][j]);
	}

	cout << f[0][len - 1];

第二种情况没找到图懒得画了。
经典例题：P1775石子合并弱化版、CF607B祖玛游戏

谈谈环形DP

常见两种方案解决：

1. 把原序列复制一遍再辅以 \(len \le n\)限制。
2. 断环为链，枚举断环，会引入一维时间复杂度，多数情况下更劣。(\(O(n^4) <- O((2n)^3)\))
3. 先按照序列问题做，然后单独分类讨论头尾边界（比如最大化环上子集和但要求至少相隔 1 个点，分类讨论 1，n 是否都选。先强制 1 不选然后强制 1 选）

树上DP

和背包问题思想重叠很大

P2015 二叉苹果树

给定一个\(n\)个结点的二叉树，满足每个结点要么是叶子，要么有两个子结点。
每条边上有若干苹果，要求砍掉一些子树（即取出一个包含根结点的连通块），求刚好剩下\(Q\)条边时，这些边苹果数之和最大是多少。
数据范围：\(1 \le Q \le n \le 100\)，每条边的苹果数\(\le 3 \times 10^4\)。

点击查看代码

const int maxn = 110;
int n, Q;
int son[maxn][2], val[maxn][2];
int dp[maxn][maxn];
int siz[maxn]; // 记录节点 i 为根的树的边数

/*
树形背包：将树的每个子树视为一个 “物品组”，选择子树中的若干条边（对应背包的 “选物品”），
然后将不同子树的选择结果合并，得到当前节点的状态。
本质是把 01 背包的 “单个物品选择” 扩展为 “子树内一组物品的选择”。*/

void dfs(int u){
    int a = son[u][0], b = son[u][1];
    if(!a && !b) return;
    dfs(a); dfs(b);
    siz[u] = siz[a] + siz[b] + 2;
    for(int i = -1; i <= siz[a]; i++) // 遍历树形背包（底层逻辑是01背包）
    for(int j = -1; j <= siz[b]; j++){ 
        // -1 表示没选这个子树且没选到这个子树的边，0表示没选这个子树但是选了到这个子树的边
        // i 表示选了到这个子树的边且这个子树选了 i 条边
        // 统计边数花费的时候，要用 (i + 1) + (j + 1)。用 -1 很自然符合式子
        int vala = i == -1 ? 0 : dp[a][i] + val[u][0]; // 不仅要记录子节点 a 子树的最优解，还要加上 u -> a 这条边的贡献
        int valb = j == -1 ? 0 : dp[b][j] + val[u][1];
        dp[u][i + j + 2] = max(dp[u][i + j + 2], vala + valb);
    }
}

int main(){
    cin >> n >> Q;
    for(int i = 2; i <= n; i++) {
        int u, v;
        cin >> u;
        int b = son[u][0] ? 1 : 0;
        cin >> son[u][b] >> val[u][b];
    }
    dfs(1);
    cout << dp[1][Q] << "\n";
	return 0;
}

P2014 [CTSC1997] 选课

给定 \(n\) 门课程来选，每门课程 \(i\) 有依赖的课程 \(k_i\)，即选了 \(k_i\) 才能选 \(i\)，如果 \(k_i = 0\) 则表示没有依赖。每门课程有一个权值 \(s_i\)，选出 \(m\) 门课，要求最大化被选的课程权值和。数据范围：$n, m ≤ 300 $

\(f_{u,w}\) 表示根为 \(u\) 的子树中，选择 \(w\) 门课程，权值和最大是多少。
在转移到父结点的时候，对于每一个子树枚举其选择了多少课程，直接枚举的话复杂度会爆炸，因为上一题固定子树个数是 2，而这一题显然是没有保证的。
简单分析发现这是一个 分组背包模型（即物品有若干类，同一类里面恰好只能选一个物品的背包模型）。

点击查看代码

const int maxn = 330;
const int inf = 0x3f3f3f3f;
int head[maxn], to[maxn], nxt[maxn];
int cnt = 0;
int dp[maxn][maxn];
int w[maxn];
int n, m;

void adde(int u, int v){
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

void dfs(int u){
    for(int i = 1; i <= n; i++)
        dp[u][i] = -inf;
    for(int v = head[u]; v; v = nxt[v]){
        dfs(v);
        static int g[maxn * 2]; // 使用滚动数组
        for(auto &gg : g) gg = -inf; 
        for(int j = 0; j <= m; j++)
        for(int k = 0; k <= m; k++){
            // 对子树进行分组背包
            /* 每个子树视为一个物品组
               选择子树内的若干条边（对应背包的选物品，i 条边就是物品 i）
               然后将不同子树的选择结果合并，得到当前节点的状态*/
            g[j + k] = max(g[j + k], dp[u][j] + dp[v][k]); 
        }
        memcpy(dp[u], g, (m + 1) << 2);
    }
    if(u == 0) return;
    // 考虑当前根选不选
    for(int i = m; i; i--)
    dp[u][i] = dp[u][i - 1] + w[u];
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int k;
        cin >> k >> w[i];
        adde(k, i);
    }
    dfs(0);
    cout << dp[0][m] << "\n";
	return 0;
}