【动态规划笔记】区间DP

作者：

Aigrl , 2022-04-20 17:38:35 , 所有人可见 , 阅读 42

笔记汇总

区间$DP$ 指在一段区间上进行动态规划，一般做法是由 长度较小的 区间往 长度较大的 区间进行递推，最终得到整个区间的答案。

一道题目是否可以用区间$DP$，可通过：

是否是最优化问题，是否无后效性，如多个 合法状态 并列组成的状态也是一个 合法状态

考虑如何设定 动态规划 的阶段，

既可以表示出初始每个状态的费用，也可以表示出合并后整个状态的费用

因为区间$DP$ 只能合并 相邻的 两个状态，

所以需要在合并前确定 所合并的两个状态是相邻的，这要求我们储存这两个状态的 左右端点。

由于转移数组需要存最优值，我们将这个任务交给了数组状态。

这也便于我们表示中间状态，但是，怎样确定选了的一定是合适的，

好吧，我们可以将所有初始状态看作是树的叶子，求终值就是一个由下往上更新的过程，

但所有相邻的叶子都可能连边，为了不漏连，我们要先尝试所有连向了 同一结点 的子节点，

其中连的点，可能是叶子，也可能是大结点（子节点有很多叶子），它们都得是已经算出答案的上层。

这启发我们按区间长度来规划。

    //预处理前缀和（DP状态转移中会频繁的用到区间和）
    for (int i = 1; i <= n << 1; ++ i) s[i] = s[i - 1] + w[i];

    memset(f, -0x3f, sizeof f);//求最大值预处理成最小值（可以省掉，这题不会有负数状态所以0就是最小）
    memset(g, +0x3f, sizeof g);//求最小值预处理成最大值（不可省掉）

    for (int len = 1; len <= n; ++ len)//阶段
    {
        for (int l = 1, r; r = l + len - 1, r < n << 1; ++ l)//左右区间参数
        {
            if (len == 1) f[l][l] = g[l][l] = 0;  //初始状态，不用合并
            else
            {
                for (int k = l; k + 1 <= r; ++ k) //枚举分开点
                {
                    f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]),
                    g[l][r] = min(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }
    }