动态规划基础

What · 是什么

动态规划（Dynamic Programming, DP）将原问题分解为重叠子问题，用状态描述子问题、用状态转移方程描述子问题间关系，按序求解避免重复计算。三要素：最优子结构（原问题最优解含子问题最优解）、无后效性（已解子问题不受后续决策影响）、子问题重叠（同一子问题被多次需要，可缓存）。DP 的本质是在状态构成的 DAG 上求最长/短路。

Why · 为什么

How · 实现

伪代码

# 数字三角形 DP
def dp(triangle):
    r = len(triangle)
    f = [row[:] for row in triangle]  # f[i][j] = 从顶到(i,j)最大和
    for i in range(1, r):
        for j in range(i + 1):
            best = f[i-1][j] if j < i else -inf
            if j > 0: best = max(best, f[i-1][j-1])
            f[i][j] += best
    return max(f[r-1])

Python 实现

# 动态规划基础：数字三角形 + LCS（含自测）

def triangle_dp(triangle):
    """数字三角形: 从顶到底路径最大和
    triangle[i] 是长度 i+1 的列表"""
    r = len(triangle)
    if r == 0:
        return 0
    f = [row[:] for row in triangle]  # f[i][j] = 从顶到 (i,j) 的最大和
    for i in range(1, r):
        for j in range(i + 1):
            # 只能从左上 (i-1,j-1) 或正上 (i-1,j)
            up_left = f[i - 1][j - 1] if j > 0 else float('-inf')
            up = f[i - 1][j] if j < i else float('-inf')
            f[i][j] += max(up_left, up)
    return max(f[r - 1])

def lcs_length(a, b):
    """最长公共子序列长度, O(nm)"""
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

if __name__ == "__main__":
    # 数字三角形 (IOI1994 示例)
    tri = [
        [7],
        [3, 8],
        [8, 1, 0],
        [2, 7, 4, 4],
        [4, 5, 2, 6, 5],
    ]
    assert triangle_dp(tri) == 30  # 7→3→8→7→5
    # LCS
    assert lcs_length("abcde", "acde") == 4
    assert lcs_length("AGGTAB", "GXTXAYB") == 4  # GTA
    # 单元素
    assert triangle_dp([[42]]) == 42
    print("dp-basic OK")

易错点

• 状态定义不当——没有正确刻画子问题，导致转移方程写不出或错误
• 不满足无后效性（后续决策影响已算子问题）→ 需扩充状态维度消除后效
• 转移方程遗漏决策（如 LCS 只考虑了匹配忘记跳过）
• 二维数组未正确独立创建（引用陷阱）导致结果串扰
• 忽略边界/初始状态（如 dp[0][0] 未正确设置）

例题

信源

• OI Wiki✓ https://oi-wiki.org/dp/basic/
• CP-Algorithms✓ https://cp-algorithms.com/dynamic_programming/intro-to-dp.html
• 书籍✓ CPH ch7 p75