Day 25 · 线性 DP：四步法与三大模型

题意：给一个数字金字塔，从塔尖出发往下走，每一步可以到左下方或右下方的格子，一直走到最底部（在哪一格停下都行）。问走过的数字之和最大是多少。

思路

把「从塔尖走到 (i,j) 的最大和」翻过来想，改成「从 (i,j) 走到最底部的最大和」，然后自底向上递推：

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

最后一行没有下一步，直接等于自己的数字（边界）；答案就是塔尖 dp[1][1]。

为什么不用自顶向下？因为自顶向下时每一行的左右两条斜边都只有一个"父亲"，得特判；自底向上时每个格子下面都正好有两个格子，一个特判都不用写（详见本文第 3 节的对比表）。

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

30

完整代码

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

// r <= 1000，全局数组自动清零
int dp[1005][1005];

int main(){
    ios::sync_with_stdio(false);   // 最多要读 50 万个数，关掉同步更快
    cin.tie(NULL);

    int r;
    cin >> r;

    // 直接读进 dp 里，省一个数组
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= i; j++)
            cin >> dp[i][j];

    // ★ 自底向上：先把最后一行当成「从该点走到最底部的最大和」
    for(int i = r - 1; i >= 1; i--)
        for(int j = 1; j <= i; j++)
            dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);

    cout << dp[1][1] << endl;      // ④ 答案就是塔尖
    return 0;
}

易错点

• 数组开小：dp[1005][1005] 是安全值。下标从 1 开始用，而且转移要读 i+1 行，别只开 1001。
• 写成局部数组：局部数组不初始化是随机值。要么开全局，要么写 = {0}。
• 手推一遍样例再交：这题的错误九成出在边界上，手推能当场发现。
• 数字虽然都是非负的，但这题不涉及"和可能为负"的问题；等到做 P1115 最大子段和时才要注意「全为负」的情况。

题意：棋盘上卒在 (0,0)，要走到 (n,m)，只能向下或向右走一步。棋盘上有一匹不动的马，马自己所在的点以及它一步能跳到的 8 个点都是禁区，卒不能经过。问从起点到终点有多少条合法路径。

思路

四步法：

① dp[i][j] = 从起点走到 (i,j) 的路径条数；
② dp[i][j] = dp[i-1][j] + dp[i][j-1]（因为是数方案，所以用加法）；
③ 起点 dp[起点] = 1，马的控制点全部置 0；
④ 答案 dp[n][m]。

两个实现要点：

(1) 坐标整体平移 +2。所有坐标加上 2（起点变成 (2,2)），这样 dp[i-1][j] 在 i=2 时读到的是 dp[1][j] = 0，天然表示"棋盘外面走不进来"，不用写任何边界特判。
(2) 9 个控制点。马自己的位置也算一个，漏了就错。

6 6 3 3

6

完整代码

#include <iostream>
using namespace std;

// ★ 路径条数会超过 int（20x20 棋盘最大约 1.4e11），必须 long long
long long dp[30][30];
bool blocked[30][30];

int main(){
    int n, m, hx, hy;
    cin >> n >> m >> hx >> hy;

    // 整体平移 2 格，这样 dp[i-1][j]、dp[i][j-1] 不会用到负下标
    n += 2; m += 2; hx += 2; hy += 2;

    // 马自己 + 8 个跳跃点，一共 9 个控制点（第一个 (0,0) 就是马自己！）
    int dx[9] = { 0, -2, -1,  1,  2,  2,  1, -1, -2};
    int dy[9] = { 0,  1,  2,  2,  1, -1, -2, -2, -1};
    for(int k = 0; k < 9; k++){
        int x = hx + dx[k], y = hy + dy[k];
        if(x >= 0 && y >= 0) blocked[x][y] = true;
    }

    dp[2][2] = 1;                       // 起点（平移后是 (2,2)）
    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m; j++){
            if(blocked[i][j]){ dp[i][j] = 0; continue; }   // 控制点走不到
            if(i == 2 && j == 2) continue;                 // 起点不参与转移
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

易错点

• 用 int 存 dp 和答案 —— 本题第一大坑。答案上界约 1.38×10¹¹，必须 long long。
• 控制点只标 8 个 —— 马自己也是禁区，一共 9 个。写 9 个元素的偏移量数组最不容易漏。
• 忘了平移坐标 —— 直接从 (0,0) 开始递推，会读到 dp[-1][j]，越界或玄学错误。
• 起点 dp[2][2] = 1 之后，循环里要 continue 跳过它，否则会被 dp[1][2] + dp[2][1] = 0 覆盖成 0。
• 标记控制点时判断 x >= 0 && y >= 0，防止写到数组外面去。

题意：有一面 2 行 N 列的墙，手里有 2×1 的骨牌和 L 型（2×2 挖掉一角的 3 格）砖，两种砖都能随便旋转、无限量供应。问把整面墙不重不漏铺满一共有多少种铺法；因为答案很大，只输出末 4 位（不足 4 位就直接输出，不加前导 0）。

思路

四步法：

① f[n] = 把 2×n 的墙铺满的方案数；
② f[n] = f[n−1] + f[n−2] + 2·S[n−3]（S[m] = f[0]+…+f[m] 是前缀和）；
③ 边界 f[0] = 1（空墙 = 什么都不铺，也算 1 种）、f[1] = 1、f[2] = 2；
④ 答案 f[N] % 10000。

转移方程的三个来源，就是「左上角那一格被哪块砖盖住」的三种情况（详细推导见本文第 6 节）：

其中 L 那一类展开就是 Σj=3..n 2·f[n−j] = 2·(f[0]+f[1]+…+f[n−3])。用前缀和把它压成 O(1)，整个算法就是一遍 O(N) 递推。

13

3465

题面明确说了 2×13 的铺法数是 13465，取末 4 位才是 3465。也就是说，只有真的算出 13465 再取模才会得到 3465 —— 这个样例顺便能验证我们的取模位置没写错。

完整代码

#include <iostream>
using namespace std;

const int MOD = 10000;

// f[n]：2 x n 墙壁的覆盖方案数
// S[n]：f[0] + f[1] + ... + f[n]，用前缀和把转移压成 O(1)
int f[1000005];
int S[1000005];

int main(){
    int N;
    cin >> N;

    // 边界：空墙 1 种；2x1 只能竖放一块 1 种；2x2 可以两块竖放、也可以两块横放，2 种
    f[0] = 1;
    f[1] = 1;
    if(N >= 2) f[2] = 2;

    S[0] = f[0] % MOD;
    if(N >= 1) S[1] = (S[0] + f[1]) % MOD;
    if(N >= 2) S[2] = (S[1] + f[2]) % MOD;

    // f[n] = f[n-1] + f[n-2] + 2 * S[n-3]
    for(int i = 3; i <= N; i++){
        f[i] = (f[i - 1] + f[i - 2] + 2 * S[i - 3]) % MOD;
        S[i] = (S[i - 1] + f[i]) % MOD;      // S 会越滚越大，必须每步取模
    }

    cout << f[N] << endl;
    return 0;
}

易错点

• 转移里现场扫一遍前缀求和：那是最直观但最慢的写法，O(N²)，N = 10⁶ 必超时。要用前缀和数组 S 把它变成 O(1)。
• S 忘记取模：S 是累加量，不取模会涨到 10¹⁰，int 直接溢出成负数。
• 漏掉 f[0] = 1：它对应「L 阶梯正好铺满整面墙、右边一列不剩」这种情况。少了它 N = 3 会算成 3 而不是 5。
• 手动补前导零：N = 3 要输出 5，不是 0005。用整数取模输出即可。
• 分类分漏了：一定要检查「竖 / 横 / L」三类是不是既互不重叠、又覆盖了全部情况（就是第 6 节那句「不重不漏」）。
• 数组要开到 10⁶ 级别。两个 int 数组约 8 MB，没问题；但别开成 long long 的多维数组。

题意：n 个同学站成一排，每人有身高。请走最少的人，使剩下的人排成「合唱队形」：存在一个最高点，最高点左边严格递增、右边严格递减。问最少请出去几个人。

思路

枚举「最高点」是哪个同学（设为 i），那么：

· 左边最多留 up[i] 个人 —— 以 i 结尾的最长严格上升子序列；
· 右边最多留 down[i] 个人 —— 以 i 开头的最长严格下降子序列。

于是以 i 为最高点能留下 up[i] + down[i] - 1 个人（i 被两边各数了一次，要减 1）。

把所有 i 试一遍取最大，答案 = n − 最多能留下的人数。

求 up[] 是正着扫一遍 LIS；求 down[] 是倒着扫一遍，找 j > i 且 t[j] < t[i] 的转移。

8
186 186 150 200 160 130 197 220

4

样例最优方案：留下 150 200 160 130（先升到 200，再一路降到 130），共 4 人，所以请出去 8 − 4 = 4 人。

完整代码

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

int t[105];
int up[105];      // up[i]：以 i 结尾的最长「严格上升」子序列长度
int down[105];    // down[i]：以 i 开头的最长「严格下降」子序列长度

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

    // 正着扫一遍：上升的 LIS
    for(int i = 1; i <= n; i++){
        up[i] = 1;
        for(int j = 1; j < i; j++)
            if(t[j] < t[i]) up[i] = max(up[i], up[j] + 1);   // 严格上升
    }

    // 倒着扫一遍：等价于「以 i 为最高点的下降部分」
    for(int i = n; i >= 1; i--){
        down[i] = 1;
        for(int j = i + 1; j <= n; j++)
            if(t[j] < t[i]) down[i] = max(down[i], down[j] + 1);
    }

    int best = 0;
    for(int i = 1; i <= n; i++)
        best = max(best, up[i] + down[i] - 1);   // i 这个最高点被数了两次，减 1

    cout << n - best << endl;                    // 出列人数 = 总人数 - 留下的
    return 0;
}

易错点

• 答案写成 best 而不是 n - best：题目问「最少请出去几个人」，不是「最多留几个人」。看清问的是哪个。
• 忘了减 1：up[i] + down[i] 把最高点 i 数了两次，正确是 up[i] + down[i] - 1。
• 判断条件写成 <=：题目要严格递增/递减，必须写 t[j] < t[i]。
• down 的方向搞反：down[i] 是「以 i 开头往右走」，所以倒着扫、从 j = i+1 开始，条件也是 t[j] < t[i]（比 i 矮的才能接在后面）。
• 最高点可以在最左端或最右端（此时一边为空），代码天然支持，不用特判。