31 · 动态规划入门：线性 DP 四步法

DP 不是一种算法，是一种把“重复计算”换成“查表”的写法。数字三角形 n = 1000 层，从顶到底的路径有 2⁹⁹⁹ 条，暴搜到宇宙热寂也跑不完；但互不相同的子问题只有 n(n+1)/2 ≈ 5×10⁵ 个。同一个子问题被重复算了天文数字次，DP 的全部工作就是让每个子问题只算一次、把结果存进数组。

• ① 状态：用 dp[...] 的下标把子问题编码出来，数组的值就是这个子问题的答案。判断状态定得好不好，只看一条——能不能用规模更小的状态把当前状态算出来。
• ② 转移：dp[当前] = 若干 dp[更小规模] 的 max / min / 和。本质是分类讨论“最后一步从哪来”，把所有来源列全，一个不漏。
• ③ 边界：最小的、不需要转移就能直接写出来的状态，通常是 dp[0] 或第一行。边界写错，整张表都是垃圾。
• ④ 答案：最终输出哪个格子？dp[n]？dp[n][n]？还是 max(dp[n][1..n])？至少三分之一的 WA 出在这一步。

无后效性是 DP 能不能用的唯一门槛：一个状态一旦确定，之后怎么走与“怎么走到这里”无关。数字三角形里 dp[i][j] 只记“走到 (i,j) 的最大和”，不需要知道具体走了哪条路——满足。如果题目改成“路径上不许出现两个相邻的相同数字”，dp[i][j] 立刻不够用，因为还得记住上一格是谁。

判断方法是一句话：要算出下一个状态，我还需要知道历史里的什么？答案是“什么也不需要”，直接 DP；答案是“需要知道某段历史”，就在下标里加一维把那点历史记下来。下一节背包多出来的那一维（选没选过）、后面状压 DP 多出来的那一维（哪些点走过），都是这个思路。

// 反例：状态里没有“以 i 结尾”这个信息
int dp[1005];   // dp[i]：前 i 个数的 LIS 长度（错）
// a = {5, 1, 2, 3}
// 前 2 个数 {5,1} 的 LIS 是 1，可 a[2]=1 后面还能接上 2、3
// dp[i] 与 dp[i-1] 之间根本没有可用的转移式：a[i] 可能不在最优解里

// 正例：把“最后一个元素是谁”钉进下标
int f[1005];    // f[i]：以 a[i] 结尾的 LIS 长度（对）
// f[i] = 1 + max{ f[j] : j < i 且 a[j] < a[i] }

const int INF =  0x3f3f3f3f;      //  1061109567
const int NEG = -0x3f3f3f3f;      // -1061109567

int dp[1005];

memset(dp, 0, sizeof dp);          // 全 0：求最大值且不要求“恰好”时用
fill(dp, dp + n + 1, NEG);         // 全 −INF：求最大值且要求“恰好凑出”时用
fill(dp, dp + n + 1, 0);           // 只清前 n+1 个：多测时用它，省掉清整张 10⁶ 的表

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;         // n ≤ 1000，开 1005 让下标 1000 安全
int a[MAXN][MAXN];             // 原始数字三角形
int dp[MAXN][MAXN];            // dp[i][j]：从顶走到 (i,j) 的最大路径和

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // ③ 边界：起点没有“上面”，它的路径和就是它自己
    dp[1][1] = a[1][1];

    // ② 转移：按行推进。第 i 行只依赖第 i-1 行，所以“按行的顺序”天然就是合法的计算顺序
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j <= i; ++j) {
            if (j == 1)                       // 左边缘：没有左上格子，只能从正上方来
                dp[i][j] = a[i][j] + dp[i - 1][j];
            else if (j == i)                  // 右边缘：没有正上格子，只能从左上方来
                dp[i][j] = a[i][j] + dp[i - 1][j - 1];
            else                              // 中间：两个前驱取优
                dp[i][j] = a[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j]);
        }

    // ④ 答案：底行最大值，不是 dp[n][n]
    int ans = dp[n][1];
    for (int j = 2; j <= n; ++j) ans = max(ans, dp[n][j]);

    cout << ans << "\n";
    return 0;
}

int a[1005], dp[1005];        // dp 只需要 1005 个 int

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) cin >> a[j];   // 先把这一行读进来
    for (int j = i; j >= 1; --j)                // 再倒序更新
        dp[j] = a[j] + max(dp[j - 1], dp[j]);
}
int ans = dp[1];
for (int j = 2; j <= n; ++j) ans = max(ans, dp[j]);

第二个模型：以 i 结尾。问题：给定 a[1..n]（n ≤ 1000），求最长严格上升子序列的长度。子序列可以不连续，但要保持原顺序。

int a[MAXN], f[MAXN];          // f[i]：以 a[i] 结尾的最长严格上升子序列长度

int ans = 1;
for (int i = 1; i <= n; ++i) {
    f[i] = 1;                                       // 边界：只有 a[i] 自己，长度 1
    for (int j = 1; j < i; ++j)                     // 枚举“紧挨在 i 前面的那个是谁”
        if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
    ans = max(ans, f[i]);
}

为什么状态必须写成“以 i 结尾”？因为转移时需要知道“新元素能接在谁后面”，这一点只有 i 能提供。如果把状态定义成“前 i 个数的 LIS 长度”，dp[i] 和 dp[i−1] 之间就没有可用的转移式——a[i] 可能根本不在最优解里，dp[i] 甚至可能等于 dp[i−1]，推不下去。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
int t[MAXN];        // 身高
int f[MAXN];        // f[i]：以 i 结尾的最长严格上升子序列长度
int g[MAXN];        // g[i]：以 i 开头的最长严格下降子序列长度

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // 正着推：f[i] = 1 + max{ f[j] : j < i 且 t[j] < t[i] }
    for (int i = 1; i <= n; ++i) {
        f[i] = 1;                                  // 边界：自成一串
        for (int j = 1; j < i; ++j)
            if (t[j] < t[i]) f[i] = max(f[i], f[j] + 1);
    }

    // 倒着推：g[i] = 1 + max{ g[j] : j > i 且 t[j] < t[i] }
    // 必须 i 从 n 递减，才能保证用到 g[j] 时它已经算好
    for (int i = n; i >= 1; --i) {
        g[i] = 1;
        for (int j = n; j > i; --j)
            if (t[j] < t[i]) g[i] = max(g[i], g[j] + 1);
    }

    int keep = 0;
    for (int i = 1; i <= n; ++i)
        keep = max(keep, f[i] + g[i] - 1);         // i 被两段都数了一次，减 1

    cout << n - keep << "\n";
    return 0;
}