B线性 DP

路径型 / 递推入门

数字三角形·过河卒·方格取数

本课摘要

路径型 / 递推入门课程回答“沿序列或网格推进时，如何定义最小充分状态”。内容以数字三角形·过河卒·方格取数为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

判断路径型 / 递推入门的适用条件与状态边界
围绕“数字三角形·过河卒·方格取数”推导转移与计算顺序
用演示、复杂度分析和配套题目校验实现

本课目录 · 0 节

正在整理目录…

从「一步一步往下走」说起

先看一个具体场景——数字三角形：一座数字塔，从塔顶出发往下走，每一步只能踩到正下方或右下方那一格，一直走到塔底。把沿途踩过的数字加起来，问：怎么走，能让这个总和最大？

数字塔：从顶走到底，每步只能去正下方或右下方。图中高亮的一条路 3→6→8，总和 17——它是最大的吗？

第一反应也许是贪心：每一步都挑「眼前更大的那个邻居」。从顶上 $3$ 往下，左边是 $6$ 、右边是 $5$ ，贪心选 $6$ ；再往下， $6$ 的两个孩子是 $3$ 和 $8$ ，选 $8$ ——凑成 $3+6+8=17$ 。这一回它恰好对了，但贪心并不可靠：眼前小一点的邻居，底下可能接着一串大数。此刻的最优选择，要看后面还能捡到多少——这是个牵一发动全身的全局问题。

那把每条路径都枚举一遍呢？塔有 $n$ 层，每步二选一，就是 $2^{n-1}$ 条路， $n=100$ 时是天文数字。DP 的思路，是不去数「路」，而是给每一格算一个值：从这一格出发、走到塔底能拿到的最大总和。

这里藏着线性 DP 最朴素的一问：站在一格上，往下的「最后一步」从哪来？——只可能是它正下方或右下方的那一格接上来。把这个「最后一步」想清楚，转移方程就浮出来了。

状态与转移：每格只回看下面两格

定状态。设 $f[i][j]$ 表示：从第 $i$ 行第 $j$ 列这一格出发、一路走到塔底，能得到的最大数字和。这样一来，我们真正想要的答案就是塔顶那一格 $f[1][1]$ 。

每格 f[i][j] 只有两个下方来源：正下方 f[i+1][j] 与右下方 f[i+1][j+1]，取较大的那个，再加上自己这格的数字。

站在 $f[i][j]$ ，下一步只有两条路：走到正下方 $f[i+1][j]$ ，或走到右下方 $f[i+1][j+1]$ 。从这一格出发的最大和，就是「自己这格的数字 $a[i][j]$ 」加上「两个下方谁能带来更大的后续」。于是得到转移方程：

f[i][j]=a[i][j]+\max\big(\,f[i+1][j],\ f[i+1][j+1]\,\big)

边界在最底行：站在塔底，脚下就是终点，无路可走，从这里出发的最大和就是它自己， $f[n][j]=a[n][j]$ 。有了地基，从倒数第二行开始自底向上逐行往塔顶推，最后读 $f[1][1]$ 即答案。

本质

这一步把「数 $2^{n-1}$ 条路」换成了「给 $O(n^2)$ 个格子各算一个最优值」。能这么换，靠的是无后效性： $f[i][j]$ 只关心「从这格往下」的最优，与「怎么走到这格」毫无关系。每个子问题（一格的最优）算一次、存下来，被上方两格反复复用——这正是最优子结构 + 重叠子问题，DP 的两块基石。

跟着算一遍

用图中那座三行小塔（第 1 行 $3$ ；第 2 行 $6,5$ ；第 3 行 $3,8,2$ ）走一遍，从最底行往上填：

最底行落地。 第 3 行每格脚下就是终点，从它出发的最大和就是自己：

f[3][1]=3,\ f[3][2]=8,\ f[3][3]=2

。这是整张表的地基。

算第 2 行左格

f[2][1]

（本身

a=6

）。它的两个下方是

f[3][1]=3

与

f[3][2]=8

，取大者

8

，于是

f[2][1]=6+8=14

。

算第 2 行右格

f[2][2]

（本身

a=5

）。两个下方是

f[3][2]=8

与

f[3][3]=2

，取大者

8

，于是

f[2][2]=5+8=13

。

算塔顶

f[1][1]

（本身

a=3

）。两个下方是

f[2][1]=14

与

f[2][2]=13

，取大者

14

，于是

f[1][1]=3+14=17

——正是最大和，对应那条

3\to 6\to 8

的路。

下面的演示会把整座塔从底往上逐格填满，并高亮每格的两个下方来源。试着改数字或层数，看它实时重算。

看它从底往上长出来

第0行

第1行

第2行

第3行

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

f[i][j] = a[i][j] + \max(f[i+1][j],\ f[i+1][j+1])

准备：把三角形左对齐，从最底行开始，自底向上填写每格到底部的最大路径和。

进度

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

换个方向：把「最优」换成「计数」

同一套「格子上的递推」，稍微换个问法就能解一类全新的题。看过河卒：一枚卒在网格上，从左上角出发，每步只能向右或向下，要走到右下角。这回不问「最大和」，而问一共有多少条不同的路。

还是先问那句话：走到某一格 $(i,j)$ ，最后一步从哪来？只可能从上方 $(i-1,j)$ 向下一步，或从左方 $(i,j-1)$ 向右一步。于是「走到 $(i,j)$ 的路数」= 「走到上方的路数」+「走到左方的路数」：

f[i][j]=f[i-1][j]+f[i][j-1]

边界是起点 $f[1][1]=1$ （站着没动，也算 1 条路），第一行、第一列都只有 1 条路（只能一直往右 / 往下）。和数字三角形是同一个模具：只是把转移里的 $\max$ 换成了相加——求最优变成了求方案数。

过河卒还多一条硬约束：棋盘上有一匹马，马本身和它能一步跳到的 8 个点都是障碍，卒一步都不能踩。障碍怎么进方程？很简单——障碍格的方案数直接钉成 0：既然卒到不了它，它也就不会再把任何路径数往右、往下传出去。这就是「非法状态清零」，线性 DP 里最常用的一记落子。

网格计数：每格 = 上方 + 左方。把中间 (2,2) 设成障碍（×，钉成 0）后，它不再向外传数——右下角的总路数从无障碍的 6 被截断成 2。

用一个 $3\times 3$ 的小网格验一下：不设障碍时，第一行、第一列全是 $1$ ，往里每格上+左累加，右下角得 $6$ （正是组合数 $\binom{4}{2}$ ）。一旦把正中间 $(2,2)$ 设为障碍钉成 $0$ ，穿过中心的那些路全被掐断，右下角只剩 $2$ 。一个格子清零，整张计数表随之改写。

并排看：障碍如何截断路径

道理讲完，不如亲手试。下面的网格默认 $4\times 4$ 、正中 $(2,2)$ 是障碍——点任意格子可设 / 撤障碍（起点「起」、终点「终」锁定不可点）。读数条会实时告诉你：无障碍时共几条路，避开当前障碍后剩几条，被截断了多少。演示区把每格从上方 + 左方累加的过程逐格走给你看，障碍格会标红并钉成 $0$ 。试着把障碍挪到角落，或一次设两三个，看这个计数怎么随之崩塌或复原。

无障碍共 20 条路 · 当前避开 1 个障碍后剩 8 条（障碍截断了 12 条）

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

f[i][j] = f[i-1][j] + f[i][j-1]

准备：从左上角出发，每步只向右或向下；红格是不能经过的障碍。

进度

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

记牢：非法状态钉成「零元」

「障碍清零」不是特例，而是一条通法：在求最优的题里，非法状态钉成 $-\infty$ （永远选不中）；在求方案数的题里，钉成 $0$ （贡献 0 条路）。把不合法的格子设成该问题的「零元」，它就会自动被排除在所有转移之外——比在每条转移里写一堆 $if$ 判断干净得多。

例题

P1216[USACO1.5][IOI1994] 数字三角形 Number TrianglesIOI1994普及-

题意

给一座

n

行的数字三角形，从顶到底、每步走向正下方或右下方，求路径上数字之和的最大值。

对应关系

本类型的裸模板。状态

f[i][j]

= 从

(i,j)

到底的最大和，自底向上一路推到塔顶

f[1][1]

。

转移 · 复杂度

f[i][j]=a[i][j]+\max(f[i+1][j],\ f[i+1][j+1])

，边界

f[n][j]=a[n][j]

；时间

O(n^2)

。

参考代码（自底向上）

C++

在洛谷打开 P1216

#include <algorithm>
#include <iostream>
using namespace std;
#define MX 1005
int n, a[MX][MX], f[MX][MX];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];

    for (int i = 1; i <= n; i++)         // 最底行先落地：f[n][j] = a[n][j]
        f[n][i] = a[n][i];

    for (int i = n - 1; i >= 1; i--)     // ★自底向上，从倒数第二行往塔顶推
        for (int j = 1; j <= i; j++)
            f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1]); // 正下方 / 右下方取大

    cout << f[1][1] << endl;             // 答案在塔顶
    return 0;
}
// TAG: 线性DP 数字三角形 递推

P1002[NOIP2002 普及组] 过河卒NOIP2002 普及组普及-

题意

卒从

(0,0)

只走右 / 下到达

(n,m)

，棋盘上一匹马的所在点与 8 个可跳到的点都不能经过，求不同路径条数。

换个视角（最优 → 计数）

把数字三角形的

\max

换成相加：

f[i][j]=f[i-1][j]+f[i][j-1]

，就从「求最优」跨到了「求方案数」。障碍格钉成 0 即可自动绕行。

为什么选它

两个新东西一次讲透：计数型转移（

\max\to +

）与障碍即非法状态清零。还有个必踩的坑——最坏路径数超过

2^{31}

，必须开 $\texttt{long long}$ ，否则 int 溢出。坐标从

0

起，平移成

1

-based 更好写。

参考代码（long long + 障碍清零）

C++

在洛谷打开 P1002

#include <iostream>
using namespace std;
#define MX 25
long long f[MX][MX];                 // ★路径数会爆 int，必须 long long
bool block[MX][MX];                  // 马的控制点（障碍）
int dx[9] = {0, 1, 1, 2, 2, -1, -1, -2, -2};
int dy[9] = {0, 2, -2, 1, -1, 2, -2, 1, -1};

int main()
{
    int bx, by, hx, hy;
    cin >> bx >> by >> hx >> hy;
    bx += 1, by += 1, hx += 1, hy += 1;         // 坐标从 0 起，整体平移成 1-based

    for (int k = 0; k < 9; k++)                  // 马本身 + 8 个control点设为障碍
    {
        int x = hx + dx[k], y = hy + dy[k];
        if (x >= 1 && y >= 1)
            block[x][y] = true;
    }

    f[1][1] = 1;                                 // 起点：1 条路（未走）
    for (int i = 1; i <= bx; i++)
        for (int j = 1; j <= by; j++)
        {
            if (block[i][j])                     // 障碍格：卒到不了，方案数清零
            {
                f[i][j] = 0;
                continue;
            }
            if (i == 1 && j == 1)
                continue;
            f[i][j] = f[i - 1][j] + f[i][j - 1]; // 上方来 + 左方来
        }

    cout << f[bx][by] << endl;
    return 0;
}
// TAG: 线性DP 网格路径 计数 障碍

P1004[NOIP2000 提高组] 方格取数NOIP2000 提高组普及/提高-

题意

n\times n

方格中部分格有数字，从左上角走到右下角（只走右 / 下）两次，取走沿途数字（同一格数字只算一次），求两条路径数字和的最大值。

状态设计（一条路 → 两条路同走）

难点在从「一条路径」升到「两条路径同时走」。让两条路同步推进（走过的步数相同），状态

f[i][j][k][l]

记两条路分别到

(i,j)

与

(k,l)

时的最大和；转移从两条路各自的「上 / 左」共

4

种组合取 max。若两条路撞在同一格（

i=k,\ j=l

），该格数字只能算一次，减掉重复。

为什么选它

经典的多维线性 DP / 双线程代表：把「路径型」从二维状态推到四维，是理解「多条路径联合决策」的入门题。转移骨架仍是「回看上一步的几种来源取最优」，只是来源从 2 种变成 4 种。

参考代码（四维双线程）

C++

在洛谷打开 P1004

#include <algorithm>
#include <iostream>
using namespace std;
#define MX 12
int n, a[MX][MX];
int f[MX][MX][MX][MX];               // 两条路径同时走：各自的 (x1,y1) 与 (x2,y2)

int main()
{
    cin >> n;
    int x, y, w;
    while (cin >> x >> y >> w && (x || y || w))
        a[x][y] = w;

    for (int i = 1; i <= n; i++)         // 两条路一起从 (1,1) 走到 (n,n)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                for (int l = 1; l <= n; l++)
                {
                    int best = max(max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]),
                                   max(f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1]));
                    f[i][j][k][l] = best + a[i][j] + a[k][l];
                    if (i == k && j == l)        // 同一格只能被拿一次，扣掉重复
                        f[i][j][k][l] -= a[i][j];
                }

    cout << f[n][n][n][n] << endl;
    return 0;
}
// TAG: 线性DP 网格路径 双线程 方格取数

练习

P1508Likecloud-吃、吃、吃矩阵三向最优路径：从底行中央下方出发向上走，每步可去正前 / 左前 / 右前，格中能量可正可负，求到顶行的最大能量和。数字三角形的三向版，f[i][j] 从下方三格取 max 再加自己。在洛谷打开

P1216[USACO1.5][IOI1994] 数字三角形学完回来独立默写：自底向上，f[i][j]=a[i][j]+max(下方两格)。再试着改成自顶向下（f[i][j] 由上方两格转移），体会两种方向都对。在洛谷打开

P1057[NOIP2008 普及组] 传球游戏最朴素的递推计数入门：f[i][j] = 第 i 次传球后球在第 j 人手里的方案数，每次只能传给左右邻居（环形）。转移 f[i][j]=f[i-1][左]+f[i-1][右]，答案 f[m][1]。在洛谷打开

想更直观地体会「一步一步累积」？到本部分（线性 DP）页的互动小游戏里，亲手在格子间走一条路，看每一步如何叠出最终的答案。