从两端取数：另一种拆区间的方式

石子合并里，我们靠枚举中间的分割点把区间拆成两半。但区间 DP 还有一类同样常见的场景：操作只发生在区间的两端——从两头拿、把两头删、比较两头。它们拆区间的方式不是「从中间断」，而是从两端收缩。

看一个具体博弈：桌上一排 4 个数 $a=[3,\ 9,\ 1,\ 2]$ ，两名玩家轮流行动，每回合只能从最左或最右端拿走一个数，拿到的数计入自己得分。两人都想让自己得分尽量高。先手最多能领先对手多少分？

一排数字，每回合只能从最左或最右端拿走一个；剩下的区间从两端逐步收缩。

第一反应也许是贪心：每步拿两端里更大的那个。可这并不总对——此刻贪一个大的，可能把对手放进下一步更肥的位置。因为拿走一端后，剩下的又是一个连续区间，对手同样会最优应对，牵一发而动全身。这与石子合并的困境同源：局部最优不等于全局最优，得把「剩下那段对手能拿多少」也算进来。

关键观察：无论怎么拿，当前面对的永远是一段连续区间 $[l,r]$ ；一次行动只会把它变成去掉左端的 $[l{+}1,r]$ 或去掉右端的 $[l,r{-}1]$ ——长度恰好少 1。区间结构再次浮现，这正是区间 DP 的入口，只不过转移从「枚举分割点」换成了「选哪一端」。

状态与转移：站在对手的肩膀上

定状态。设 $dp[l][r]$ 表示：当轮到某位玩家、面对区间 $[l,r]$ 时，他能取得的「自己所得 − 对手所得」的最大净胜差。用「净胜差」而非「绝对得分」，是这一类博弈 DP 的点睛之笔——它让双方都最优这件事变得可递推。

他有两种选择。若拿走左端 $a[l]$ ：这一分先进自己账户，随后对手面对子区间 $[l{+}1,r]$ ，对手在那段的最大净胜差正是 $dp[l{+}1][r]$ ——但那是站在对手视角的领先，换回我方视角要取负号。于是这一步我方净胜差 $=a[l]-dp[l{+}1][r]$ 。拿右端同理。

dp[l][r] 只有两条分支：取左端接子问题 dp[l+1][r]、取右端接 dp[l][r-1]；子区间的净胜差是对手视角，故减去。取两者较大。

dp[l][r]=\max\big(a[l]-dp[l+1][r],\ a[r]-dp[l][r-1]\big)

边界： $dp[l][l]=a[l]$ （只剩一个数，先手别无选择直接拿走，净胜差就是它）。答案： $dp[1][n]$ 即先手在整排上的最大净胜差；若还想还原先手实际得分，用总和 $S$ 反推 $\tfrac{S+dp[1][n]}{2}$ 。

同样地， $dp[l][r]$ 依赖的两个子区间 $[l{+}1,r]$ 与 $[l,r{-}1]$ 长度都比它短 1。所以递推仍不能按 $l$ 或 $r$ 顺序走，必须按区间长度由短到长——这是区间 DP 雷打不动的填表顺序。

本质

区间 DP 的两副面孔：石子合并从中间枚举分割点（一分为二，追加区间和），两端取数 / 删除类从两端收缩（每次砍掉一端，规模减一）。共同点是状态都是连续区间 $[l,r]$ 、都按长度递推。博弈型再叠一层技巧：用「净胜差」定义状态，子问题的领先在换手时取负，一个 $\max$ 就把「双方都最优」编码进了转移。

跟着算一遍

用开头的例子（ $a=[3,9,1,2]$ ，下标 $1..4$ ）走完整张三角表，重点盯住长度由短到长、以及「减去子区间」这一步：

0

对角线（长度 1）。

dp[l][l]=a[l]

：

dp[1][1]=3,\ dp[2][2]=9,\ dp[3][3]=1,\ dp[4][4]=2

。

1

长度 2：

dp[1][2]=\max(3-9,\ 9-3)=6

；

dp[2][3]=\max(9-1,\ 1-9)=8

；

dp[3][4]=\max(1-2,\ 2-1)=1

。都取「先拿大的一端」，符合直觉。

2

长度 3：

dp[1][3]=\max(a_1-dp[2][3],\ a_3-dp[1][2])=\max(3-8,\ 1-6)=-5

（这段先手反而落后）；

dp[2][4]=\max(9-1,\ 2-8)=8

。

3

长度 4，整段

[1,4]

：

\max(a_1-dp[2][4],\ a_4-dp[1][3])=\max(3-8,\ 2-(-5))=\max(-5,7)=7

。先手取右端 2、把烫手的

[1,3]

丢给对手，净胜

7

——总和 15，先手得 11、后手得 4。

下面的演示把三角表按长度一层层填满，每格高亮它选中的是「取左」还是「取右」、以及收缩后的那个子区间。改改数值，看先手的最优选择如何反转。

看三角表一层一层长出来 · 枚举分界、两段合并

r=0

r=1

r=2

r=3

l=0

l=1

l=2

l=3

3

·

9

·

1

·

2

当前计算依赖来源被选转移已确定

dp[l][l]=a[l]

对角线：只剩一个数时只能拿走它，净胜差 dp[l][l]=a[l]。

进度

已暂停，第 1 步，共 8 步，1 倍速

深化：相邻相等合并（248）与升维到二维

两端收缩是这一类的「入门形态」。把操作换成合并相邻元素并产生新值，就得到更有趣的一支——趣味十足的 248（脱胎自 2048）：一排数字，相邻两个相等的可以并成一个「值 + 1」的数，不断合并，问最终能得到的最大数字。

248 的合并规则：相邻且相等的两数并成 +1（两个 2 → 一个 3）；不相等则并不了。要合成更大的数，左右两段必须先各自缩成同一个数。

它的状态回到枚举分割点，但含义变了：设 $dp[l][r]$ = 区间 $[l,r]$ 若能反复合并缩成单个数字，则那个数字的值，否则记 $0$ （不可合成）。一段能缩成 $v{+}1$ ，当且仅当存在分割点 $k$ ，使左段 $[l,k]$ 与右段 $[k{+}1,r]$ 都能缩成同一个数 $v$ ：

dp[l][r]=\max_{l\le k<r,\ dp[l][k]=dp[k+1][r]>0}\big(dp[l][k]+1\big)

全盘答案是所有区间里最大的那个 $dp[l][r]$ ——注意不一定是整段 $dp[1][n]$ ，因为整排未必能缩成单值，但某个子段可以。这正是 248 计分「看棋盘上最大的数」的由来。下一节的演示会把这张「能否合成」的三角表画出来。

再往上一维。 一维的「合并连续区间」升到二维，就是棋盘分割（例题 P1436）：把 $8\times8$ 棋盘沿横 / 竖线递归切成若干矩形。状态从一维的 $dp[l][r]$ 膨胀成一个矩形的四个坐标 $dp[k][x_1][y_1][x_2][y_2]$ ，转移枚举「切在哪条横 / 竖线」——本质仍是枚举最后一次分割、把大区域拆成两块子区域。这条「一维合并 → 二维分割」的线，正好把区间 DP 平滑地接到 D 部分 · 网格 / 矩阵上的 DP。

看 248 怎样把相邻相等的合并起来

默认 $a=[1,1,2,2]$ ：两个 $1$ 并成 $2$ ，与原有的 $2,2$ 里的一个凑成 $2,2$ 再并成 $3$ ——全盘最大数字是 3（落在子区间 $[1,3]$ 或 $[3,4]$ 上，而整段 $[1,4]$ 反而缩不成单值）。改改数值，观察哪些格能合成（非 0）、哪些卡住。

整排能合成的最大数字 = 3 · 每格 dp[l][r] = 该区间能缩成的单一值（0 表示这段无法合成一个数）· 答案取三角表里所有格的最大值，未必在右上角。

r=0

r=1

r=2

r=3

l=0

l=1

l=2

l=3

1

·

1

·

2

·

2

当前计算依赖来源被选转移已确定

dp[l][l]=a[l]

对角线：单个数字已是一块，dp[l][l]=a[l]；0 表示区间无法缩成单值。

进度

已暂停，第 1 步，共 8 步，1 倍速

易错点：答案未必在右上角

两端取数型答案就在右上角 $dp[1][n]$ ；但 248 这类合成型，整段常常合成不了单值，右上角是 $0$ 。务必在填表过程中用一个全局变量记下所有 $dp[l][r]$ 的最大值，而不是直接输出 $dp[1][n]$ 。这是初学者在 248 上最常见的翻车点。

例题

P3146[USACO16OPEN] 248 GUSACO2016(原生P)普及+/提高

题意

一排

n

个数（

2\le a_i\le 40

）。每次可把相邻且相等的两个数并成一个「值 + 1」的数。求经过若干次合并后，能得到的最大的那个数。

对应关系

合并类区间 DP 的旗舰：

dp[l][r]

= 区间能缩成的单一值（

0

不可），枚举分割点要求左右两段合成同一个数，方能再并一级。本页深化节 + 第二演示就是它的内核。

为什么选它

2048 玩法的区间 DP 化身，趣味性极强、重交互演示天然契合。更重要的是它训练一个反直觉点：答案不是 $dp[1][n]$ ，而是全表最大值——把「区间 DP 的答案一定在整段」的思维定式打破。

转移 · 复杂度

dp[l][r]=\max_{k}(dp[l][k]+1)

（当

dp[l][k]=dp[k+1][r]>0

）；外层长度、内层左端点、最内分割点，

O(n^3)

，

n\le 248

绰绰有余。

参考代码（合成三角表 · 全表取最大）

C++

在洛谷打开 P3146

#include <iostream>
#include <algorithm>
using namespace std;

int n, a[300];
int dp[300][300];               // dp[l][r]：区间 [l,r] 能合成的单一数字（0 = 不可合成）

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[i][i] = a[i];        // 单个数自成一块
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, a[i]);
    }

    for (int len = 2; len <= n; len++)          // ★外层枚举区间长度，由短到长
    {
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            for (int k = l; k <= r - 1; k++)    // 枚举分割点：两段要合成同一个数
            {
                if (dp[l][k] && dp[l][k] == dp[k + 1][r])
                {
                    dp[l][r] = max(dp[l][r], dp[l][k] + 1);
                }
            }
            ans = max(ans, dp[l][r]);           // 答案是全盘所有区间里的最大数字
        }
    }

    cout << ans << endl;
    return 0;
}
// TAG: 区间DP 合并 248

P1436棋盘分割NOI1999提高+/省选-

题意

8\times8

棋盘，每格有分值。沿横线或竖线把棋盘切开、留一块、对另一块继续切，共切

n-1

刀得

n

块矩形。设各块总分为

x_i

、均值

\bar x

，求最小的方差

\sigma^2=\tfrac1n\sum(x_i-\bar x)^2

。

对应关系（升维）

把一维「合并 / 分割连续区间」升到二维：状态由

dp[l][r]

膨胀成矩形四坐标

f[k][x_1][y_1][x_2][y_2]

= 该矩形切成

k

块的最小平方和；转移枚举切在哪条横 / 竖线，仍是枚举最后一次分割。

为什么选它 · 衔接 D 部分

均值固定时最小方差 ⇔ 最小 $\sum x_i^2$ ，先把目标化简，是本题第一关。二维前缀和

O(1)

取矩形和、记忆化搜索而非循环填表，都是从一维区间 DP 向网格 / 矩阵 DP 过渡的钥匙——正好承上启下接到 D 部分。

转移 · 复杂度

f[k][R]=\min\big(f[k_1][R_1]+f[k-k_1][R_2]\big)

（

R_1,R_2

是

R

被某条横 / 竖线切出的两个子矩形），枚举切线与

k_1

；状态

O(n\cdot 8^4)

、每态枚举

O(8\cdot n)

，

n\le 15

轻松通过。

参考代码（二维前缀和 · 记忆化分割）

C++

在洛谷打开 P1436

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
int n;
int s[9][9];                    // 二维前缀和：s[i][j] = 左上角 (1,1) 到 (i,j) 的总和
int f[16][9][9][9][9];          // f[k][x1][y1][x2][y2]：把该矩形切成 k 块的最小平方和

// 矩形 (x1,y1)-(x2,y2) 的总分
int sum(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

int sq(int v)
{
    return v * v;
}

// 记忆化：把矩形切成 k 块，返回最小的「各块得分平方和」
int dfs(int k, int x1, int y1, int x2, int y2)
{
    int &cur = f[k][x1][y1][x2][y2];
    if (cur != -1)
    {
        return cur;
    }
    if (k == 1)                                 // 不再切，整块贡献一份平方
    {
        return cur = sq(sum(x1, y1, x2, y2));
    }
    cur = INF;
    for (int x = x1; x <= x2 - 1; x++)          // 横切：上 k1 块 + 下 k-k1 块
    {
        for (int k1 = 1; k1 <= k - 1; k1++)
        {
            cur = min(cur, dfs(k1, x1, y1, x, y2) + dfs(k - k1, x + 1, y1, x2, y2));
        }
    }
    for (int y = y1; y <= y2 - 1; y++)          // 竖切：左 k1 块 + 右 k-k1 块
    {
        for (int k1 = 1; k1 <= k - 1; k1++)
        {
            cur = min(cur, dfs(k1, x1, y1, x2, y) + dfs(k - k1, x1, y + 1, x2, y2));
        }
    }
    return cur;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= 8; i++)
    {
        for (int j = 1; j <= 8; j++)
        {
            cin >> s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }

    memset(f, -1, sizeof(f));
    int tot = sum(1, 1, 8, 8);
    // 最小方差 ⇔ 最小平方和：σ² = (Σxᵢ²)/n − x̄²，均值固定，只需最小化 Σxᵢ²
    double variance = (double)dfs(n, 1, 1, 8, 8) / n - (double)tot / n * tot / n;
    printf("%.3lf\n", variance);
    return 0;
}
// TAG: 区间DP 二维 记忆化 棋盘分割

练习

P2858[USACO06FEB] Treats for the Cows G/S 奶牛零食两端取数区间 DP 的直接应用：每天只能从零食序列最左或最右端取一个，第 t 天取出的价值要乘以天数 t。设 dp[l][r] 为取完区间 [l,r] 能得的最大加权总和，剩余天数 = 已取个数决定权重；从两端收缩、按长度递推。在洛谷打开

P2426删数删除区间合并代价：dp[l][r] 表示删空区间 [l,r] 的最大收益。既可单个删（价值 a[i]），也可把两端 a[l]、a[r] 一起删得 (a[l]+a[r]+距离)，中间那段先删空。枚举分割点 / 端点配对，按长度递推。在洛谷打开

P2196[NOIP1996 提高组] 挖地雷选取 / 路径变形（DAG 上区间不必连续）：地窖间单向连通，dp[i] = 以第 i 个地窖结尾的最大地雷数，转移取所有能到 i 的前驱最优值再加 a[i]；记录前驱以回溯输出路径。是区间 / 选取型 DP 的温和入门。在洛谷打开

合并 / 删除类

本课摘要