8. 动态规划

动态规划 (Dynamic Programming, DP) 适用的问题通常有两个特征：同一子问题会被重复求解，且原问题的最优解可以由子问题的最优解组合得到。使用动态规划时，需要把问题划分为一组按一定顺序求解、结果可以复用的子问题，称为状态；再写出由已知状态求出新状态的转移方程。

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

如果直接递归求解时，同一个子问题（例如同一段区间、同一对下标、同一剩余容量）被反复求解，即存在重叠子问题，就可以考虑改用动态规划。另一个条件是最优子结构：问题的最优解可以由规模更小的子问题的最优解组合得到。最长公共子序列、背包和编辑距离都满足这两个条件。如果后续决策依赖的历史信息无法用规模可以接受的状态描述，就不适合直接用动态规划建模。

2. 状态、转移、边界

设计动态规划算法需要确定三件事。状态描述求解进行到了哪一步，它必须包含后续决策需要的全部信息，但不应包含无关的细节。转移描述状态之间的依赖关系，通常是对若干个已知状态取 max、min 或求和。边界条件给出递推的起点，决定 DP 表能否被正确填满。动态规划程序的错误多来自边界条件遗漏或下标含义前后不一致，因此编写代码前，应先用一句话写明状态的含义。

3. 两种实现路径

记忆化搜索 (memoization) 和自底向上填表是同一组转移方程的两种计算顺序。记忆化搜索的写法与递归式一一对应，代码短，便于推导；自底向上填表没有递归调用，计算顺序明确，也更容易压缩空间。可以先写记忆化版本验证状态定义是否正确，再改写为迭代版本以提高效率。

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

下面的程序用数组 memo 缓存已经计算过的斐波那契数，使每一项只计算一次，时间复杂度为 $O (n)$ 。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，则只能不选，dp[i][c] = dp[i-1][c]；否则取 dp[i-1][c] 与 dp[i-1][c - w[i]] + v[i] 中的较大者。第 7 节的空间压缩也基于这一状态定义。

#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]，则 dp[i][j] = dp[i-1][j-1] + 1；否则取 dp[i-1][j] 与 dp[i][j-1] 中的较大者。填表完成后，从 dp[n][m] 开始逆向回溯，可以恢复一条最长公共子序列。

#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 背包为例，空间复杂度从 $O (n C)$ 降为 $O (C)$ 。容量必须从大到小枚举，这样读取 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;
        }
    }
}

这段代码是第 5 节二重循环的一维写法，其中 dp 是长度为 cap + 1、初值全为 0 的数组。

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

常见的错误之一是状态含义前后不一致，例如一段代码把 dp[i][j] 当作前缀长度为 i 的结果，另一段代码又把 i 当作下标，导致边界与转移互相矛盾。另一个常见错误是遗漏初值，特别是没有用明确的哨兵值标记不可达状态，使 max 或 min 把不合法的路径也计算在内。检查时，可以先写出状态的含义，逐一核对各循环的边界是否与之一致，再用最小的样例手工填一遍表格，确认每个格子的值都来自正确的状态。

9. 习题

#35801

⚡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)$ 。

#35802

⚡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] 在每次更新前后的语义，并用最小样例验证不能重复选择同一件物品。

#35803

⚡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})$ 动态规划，并说明状态含义与转移。

#35804

⚡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)$ 。
说明第一行、第一列和普通格子的边界转移，并用至少一个存在多条等价最优路径的样例测试。

#35805

⚡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. 习题