8. 动态规划

动态规划（Dynamic Programming, DP）解决的问题通常有两个共性：同一子问题会被重复求解，且原问题的最优解可以由子问题的最优解组合出来。它的核心不是“背公式”，而是把问题拆成一组有顺序、可复用的状态对象，并把“如何从已知状态推到下一个状态”写成稳定的转移关系。只要状态定义正确、边界条件完整，代码就会自然地收敛到正确答案。

1. 什么时候该考虑动态规划

如果一个问题在直接递归时出现明显的重叠子问题，例如同一段区间、同一对下标、同一剩余容量被反复访问，那么它就非常适合改写成动态规划。另一个常见信号是“最优子结构”：当前最优结果可以由更小规模问题的最优结果拼接而来。比如最长公共子序列、背包、编辑距离都满足这个条件；而某些需要全局历史且无法压缩到有限状态的信息，就不适合用 DP 直接建模。

2. 状态、转移、边界

动态规划的主线可以写成一句话：先定义状态，再定义转移，最后补全边界。状态是一个“描述局部进度的对象”，它必须足够表达后续决策所需的信息，又不能把无关细节也带上；转移是状态之间的有向关系，通常体现为 max/min/+ 之类的组合；边界是递推的起点，它决定了整张 DP 表是否能被正确填满。很多错误都来自边界漏写或下标语义前后不一致，因此在落代码前把状态含义写成一句自然语言，通常能显著减少返工。

3. 两种实现路径

记忆化搜索和自底向上填表本质上是同一组转移关系的两种执行顺序。记忆化搜索更贴近数学递归，代码短、推导直观；自底向上更容易做空间压缩，也更可控。一般可以先写记忆化版本验证状态定义，再改成迭代版本追求性能。这样做可以把“正确性”和“效率”分开处理，定位问题会更清晰。

4. 示例一：斐波那契的记忆化搜索

下面这段代码故意选择了最小模型：它只展示“重叠子问题如何通过缓存消除重复计算”。memo[n] 的语义是“第 n 项的值，若为 -1 则表示尚未计算”。

#include <stdio.h>

enum { MAX_N = 93 };

static long long memo[MAX_N + 1];

static void init_memo(void) {
    for (int i = 0; i <= MAX_N; ++i) {
        memo[i] = -1;
    }
}

static long long fib(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main(void) {
    init_memo();
    int n = 50;
    printf("fib(%d) = %lld\n", n, fib(n));
    return 0;
}

可能的输出（示例）：

bash

fib(50) = 12586269025

5. 示例二：0/1 背包的自底向上写法

0/1 背包是最典型的“选或不选”模型。设 dp[i][c] 表示“只看前 i 件物品，容量上限为 c 时能达到的最大价值”。当第 i 件物品重量超过 c 时只能不选；否则在“选”和“不选”之间取较大值。这个定义的优势是语义非常稳定，后续无论做一维压缩还是路径恢复，都能保持一致。

#include <stdio.h>

enum { N = 4, CAP = 8 };

int main(void) {
    int w[N + 1] = {0, 2, 3, 4, 5};
    int v[N + 1] = {0, 3, 4, 5, 8};
    int dp[N + 1][CAP + 1] = {0};

    for (int i = 1; i <= N; ++i) {
        for (int c = 0; c <= CAP; ++c) {
            dp[i][c] = dp[i - 1][c];
            if (c >= w[i]) {
                int cand = dp[i - 1][c - w[i]] + v[i];
                if (cand > dp[i][c]) {
                    dp[i][c] = cand;
                }
            }
        }
    }

    printf("max_value = %d\n", dp[N][CAP]);
    return 0;
}

可能的输出（示例）：

bash

max_value = 12

6. 示例三：最长公共子序列（LCS）长度与回溯

LCS 的状态常定义为 dp[i][j]，表示 a 的前 i 个字符与 b 的前 j 个字符的 LCS 长度。如果 a[i-1] == b[j-1]，就来自左上角再加一；否则来自上方和左方的较大者。填表完成后，从右下角逆向回溯即可恢复一条实际公共子序列。这类“先求值，再逆向恢复解”的模式在动态规划中非常常见。

#include <stdio.h>
#include <string.h>

enum { MAX_LEN = 64 };

int main(void) {
    const char *a = "ABCBDAB";
    const char *b = "BDCABA";
    int n = (int)strlen(a);
    int m = (int)strlen(b);
    int dp[MAX_LEN][MAX_LEN] = {0};

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    char out[MAX_LEN] = {0};
    int k = dp[n][m];
    out[k] = '\0';
    int i = n;
    int j = m;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            out[--k] = a[i - 1];
            --i;
            --j;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            --i;
        } else {
            --j;
        }
    }

    printf("lcs_len = %d\n", dp[n][m]);
    printf("lcs = %s\n", out);
    return 0;
}

可能的输出（示例）：

bash

lcs_len = 4 lcs = BCBA

7. 常见优化：空间压缩

当 dp[i][*] 只依赖上一行时，可以把二维表压缩成一维数组，显著降低空间占用。以 0/1 背包为例，容量循环必须从大到小更新，这样 dp[c - w[i]] 读取到的仍是“上一轮物品”的结果；若从小到大更新，会把同一物品重复使用，语义就变成了完全背包。这个细节看似微小，但会直接改变问题类型。

for (int i = 1; i <= n; ++i) {
    for (int c = cap; c >= w[i]; --c) {
        int cand = dp[c - w[i]] + v[i];
        if (cand > dp[c]) {
            dp[c] = cand;
        }
    }
}

运行结果：该代码块主要用于展示状态更新顺序，单独运行通常无终端输出。

8. 写 DP 代码时最容易出错的点

最常见的问题不是转移公式本身，而是状态语义漂移：前半段代码把 dp[i][j] 当“前缀”，后半段又当“下标本身”，结果边界和转移互相冲突。另一个高频错误是初值遗漏，尤其是“不可达状态”没有用清晰哨兵值区分，导致后续 max/min 把非法路径也混进来了。解决这类问题的办法通常很直接：先写一句完整语义，再对照语义检查每个循环边界是否一致，最后用最小样例手推一遍表格，确认每个格子的来源都可解释。

9. 习题

#30803

⚡4⏳3

实现两个字节序列之间的编辑距离：

#include <stdbool.h>
#include <stddef.h>

bool edit_distance(
    const unsigned char *left,
    size_t left_count,
    const unsigned char *right,
    size_t right_count,
    size_t *out_distance
);

一次操作可以插入一个字节、删除一个字节或替换一个字节，每次操作的代价均为 1。

要求：

返回把 left 转换成 right 所需的最少操作次数。
长度为 0 时，对应序列指针可以为 NULL。
只保存动态规划表的一行，额外空间复杂度为 $O (min (n, m))$ 。
检查行存储的大小计算和分配结果。
参数无效或无法完成计算时返回 false，并保持输出对象不变。
时间复杂度为 $O (n m)$ 。

#30804

⚡4⏳3

实现 0/1 背包：每件物品最多选择一次，求容量不超过 capacity 时的最大总价值：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool knapsack_01(
    const size_t *weights,
    const uint64_t *values,
    size_t count,
    size_t capacity,
    uint64_t *out_value
);

要求：

重量为 0 的物品也只能选择一次；输入数组不得修改。
参数无效、容量数组分配失败或价值加法溢出时返回 false，并保持输出对象不变。
使用一维状态数组，并从大到小更新容量，时间复杂度为 $O (n C)$ ，额外空间复杂度为 $O (C)$ 。
明确 dp[c] 在每次更新前后的语义，并用最小样例验证不能重复选择同一件物品。

#30805

⚡3⏳3

实现严格最长递增子序列的长度：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool lis_length_i64(
    const int64_t *items,
    size_t count,
    size_t *out_length
);

要求：

子序列保持原顺序，且相邻选中元素必须严格递增；相等元素不能同时计入同一条子序列。
count == 0 时返回长度 0，此时 items 可以为 NULL。
参数无效或辅助数组分配失败时返回 false，不得修改输出对象。
先使用“以第 i 个元素结尾”的状态写出 $O (n^{2})$ 动态规划，并说明状态含义与转移。

#30806

⚡4⏳3

给定按行优先保存的非负代价网格，只能向右或向下移动，求从左上角到右下角的最小总代价：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool minimum_grid_path(
    const uint64_t *costs,
    size_t rows,
    size_t columns,
    uint64_t *out_cost
);

要求：

rows == 0 或 columns == 0 时结果为 0；非空网格指针必须有效。
行列乘积溢出、路径代价加法溢出或参数无效时返回 false，输出对象保持不变。
额外空间复杂度必须为 $O (c o l u m n s)$ ，时间复杂度为 $O (r o w s \times c o l u m n s)$ 。
说明第一行、第一列和普通格子的边界转移，并用至少一个存在多条等价最优路径的样例测试。

#30807

⚡4⏳4

对两个任意字节序列求最长公共子序列，并重建其中一条确定的结果：

#include <stdbool.h>
#include <stddef.h>

bool lcs_u8(
    const unsigned char *left,
    size_t left_count,
    const unsigned char *right,
    size_t right_count,
    unsigned char *out_sequence,
    size_t capacity,
    size_t *out_length
);

要求：

结果必须同时是两个输入的子序列，保持各自在原序列中的相对顺序；结果长度必须最大。输入不是以空字符结尾的字符串，不能调用字符串长度或比较函数。
left_count == 0 或 right_count == 0 时成功返回长度 0；对应指针可以为 NULL。非空序列指针和 out_length 必须有效；当最大长度大于 0 时，out_sequence 也必须有效且 capacity 足够。
参数无效、行列乘积溢出或辅助存储分配失败时返回 false，不得修改输出数组和 *out_length。
使用完整的二维动态规划表，时间复杂度为 $O (n m)$ ，额外空间复杂度为 $O (n m)$ ；写出状态含义、相等字节时的转移，以及从表格回溯到输出数组的过程。
当两个候选子问题长度相等时采用固定的决策（例如回溯时优先向上），使相同输入总能得到相同的输出；输出数组不追加空字符。

3.10 求值

4.3 选择语句

5.5 跳转语句

10.2 结构体

14.3 程序支持

15.1 声明

16.2 对象表示

18.2 标准库中的宏

8. 动态规划 ​

1. 什么时候该考虑动态规划 ​

2. 状态、转移、边界 ​

3. 两种实现路径 ​

4. 示例一：斐波那契的记忆化搜索 ​

5. 示例二：0/1 背包的自底向上写法 ​

6. 示例三：最长公共子序列（LCS）长度与回溯 ​

7. 常见优化：空间压缩 ​

8. 写 DP 代码时最容易出错的点 ​

9. 习题 ​

8. 动态规划

1. 什么时候该考虑动态规划

2. 状态、转移、边界

3. 两种实现路径

4. 示例一：斐波那契的记忆化搜索

5. 示例二：0/1 背包的自底向上写法

6. 示例三：最长公共子序列（LCS）长度与回溯

7. 常见优化：空间压缩

8. 写 DP 代码时最容易出错的点

9. 习题