动态规划算法入门介绍 Dynamic Programming，DP

老马啸西风2025年10月5日大约 7 分钟

动态规划（Dynamic Programming，DP） — 详细介绍

一句话概念

动态规划就是把一个复杂问题拆成相互重叠的子问题，把子问题的答案记下来（记忆化或表格），避免重复计算，从而高效求解。

核心是最优子结构 + 重叠子问题。

两条核心性质

最优子结构（Optimal substructure）：问题的最优解可以由若干子问题的最优解构成。
重叠子问题（Overlapping subproblems）：子问题之间有重复，直接递归会大量重复计算。

设计 DP 的标准 6 步（解决一题的流程）

定义状态（state）：明确 dp[...] 表示什么（必须能唯一表示子问题）。例如：dp[i] 表示前 i 项的最优值，或 dp[i][j] 表示前 i 个物品、容量为 j 时的最优值。
写出状态转移方程（transition）：如何从更小的子问题推导出当前状态。
确定初始值 / 边界（base case）：例如 dp[0]=...，dp[i][0]=...。
确定计算顺序：按依赖关系从小到大填表（自底向上）或用递归+记忆化（自顶向下）。
得到答案：从 dp 中读出最终答案（可能在 dp[n] 或 max(dp[i])）。
（可选）恢复解（reconstruction）：如果需要还原具体方案，额外保存“选择”信息或者从后向前回溯。

两种实现策略对比

自顶向下（递归 + 记忆化）
- 思路直观，按自然递归写法改加缓存即可。
- 便于实现复杂状态，但递归层数可能深（栈溢出风险）。
自底向上（迭代表/填表）
- 明确控制计算顺序，常更节省常数（无函数调用开销）。
- 更容易做空间优化（滚动数组）。

常见 DP 模式 / 题型（套路）

线性 DP（一维/二维）：如斐波那契、最短路径、最大和子序列等。
背包类（01 背包、完全背包、多重背包）：dp[cap] 或 dp[i][cap]。
最长子序列 / 子串（LIS/LCS/最长回文子串）：dp[i] 或 dp[i][j]。
区间 DP（区间长度作为状态）：如合并石子、区间博弈、矩阵链乘。
树形 DP：在树上 DFS 计算 dp[node]（通常子节点推父节点）。
位掩码 DP（状态是一个子集）：旅行商、集合分割，适合 n ≲ 20。
数位 DP（digit DP）：处理“满足某属性的数字个数”。
基于队列/单调队列优化的 DP：用于滑动窗口最优转移。
凸包 / 分治 / Knuth 优化：当转移满足某些单调/四边形不等式时可把复杂度从 O(n²) 降到 O(n log n) 或 O(n)。

示例 1：斐波那契（最简单的演示）

定义：F(n)=F(n-1)+F(n-2)，F(0)=0,F(1)=1。

递归（指数级）--不可取。
递归+记忆化（O(n)）：

memo = {}
def fib(n):
    if n<=1: return n
    if n in memo: return memo[n]
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

迭代（自底向上，O(n) 时间、O(1) 空间）：

def fib(n):
    if n<=1: return n
    a,b = 0,1
    for _ in range(2,n+1):
        a,b = b,a+b
    return b

示例 2：0/1 背包（经典、也很实用）

问题：有 n 个物品，每个物品重量 wt[i]、价值 val[i]，背包容量 W，每个物品最多选 1 次，求最大价值。

状态：dp[i][w] = 用前 i 件物品放入容量为 w 时的最大价值。
转移：

不选第 i 件：dp[i][w] = dp[i-1][w]
选第 i 件（若 w >= wt[i]）：dp[i][w] = dp[i-1][w-wt[i]] + val[i]
所以 dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])。

空间优化：经典技巧是把二维 dp[i][w] 压成一维 dp[w]，并且从大到小遍历容量（避免重复选同一物品）：

// Java: 0/1 背包 — 空间优化为 1D
public int knapsack01(int W, int[] wt, int[] val) {
    int n = wt.length;
    int[] dp = new int[W + 1]; // dp[w] = max value for capacity w
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= wt[i]; w--) { // 从大到小
            dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

时间复杂度：O(n * W)；空间：O(W)。

示例 3：最长递增子序列（LIS）

DP 思路（O(n²)）：令 dp[i] 表示以 nums[i] 结尾的 LIS 长度。
转移：dp[i] = 1 + max(dp[j]) 对所有 j < i 且 nums[j] < nums[i]。
代码（Java）：

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

复杂度：O(n²)。若要优化到 O(n log n)，使用耐心排序（patience）+二分技巧（维护 tails 数组），这里就不展开实现细节了，但这是常见必会的优化。

状态设计技巧（常见思路）

用索引/前缀表示“已处理到哪里”：i 表示已处理前 i 个元素。
用“容量 / 花费 /剩余资源”作为状态维度：背包类。
用“上一个选了谁/最后一个值”作为状态：如 LIS、某些序列 DP。
把问题转为“决策序列”：每一步决策是选/不选或选哪种方式。
尝试把状态压缩（只保留前一层），以节省空间。
复杂状态先用递归写出正确关系，再逐步转成表填。

常见优化手段（提高时间/空间）

滚动数组 / 1D 压缩：把 dp[i][...] 压缩到 dp[...]。
前缀和 / 差分：当转移需要区间和时用前缀和加速。
单调队列 / 滑动窗口优化：把某些线性转移降为 O(n)。
分治优化（Divide & Conquer DP）：适用于转移满足“凸性”的场景。
Knuth 优化：用于区间 DP（如最优合并石子）能把 O(n³) → O(n²)（需满足单调性）。
Convex Hull Trick（CHT）：当转移是 dp[i] = min_j (dp[j] + m_j * x_i + b_j) 的形式，可降复杂度。
位掩码 + 状态压缩：用于小 n 的子集 DP（2^n * n）。
这些优化通常需要额外的数学性质或单调性，先理解普通 DP 再考虑这些技巧。

常见容易犯的错误（以及调试建议）

状态定义不清：dp 含义模糊会导致错误转移或错误的答案读取位置。
忘记处理边界（base case）：导致越界或初始值错误。
方向错误：压缩到 1D 时若遍历方向不对会重复使用同一物品。
忽略答案的位置：有时答案不在 dp[n] 而是在 max(dp[i]) 或 min(dp[*])。
没有考虑空间/时间上界：当 W 很大或 n 很大，需要换思路（贪心、数学、近似、其他算法）。
调试建议：手工写出小样例的 dp 表，逐行填表核对；打印中间状态；写暴力解（小 n）做对照。

练习题（建议掌握的经典题型 / 难度从易到难）

斐波那契 / 爬楼梯（入门）
背包家族：01 背包、完全背包、分组背包
最长子序列 LIS（n² 与 n log n 两种方法）
最长公共子序列 LCS（二维 DP）
分割等和子集（subset sum / partition）
区间 DP：石子合并 / 矩阵链乘
树形 DP：树上独立集、路径相关 DP
位掩码 DP：旅行商（TSP）小规模
数位 DP：统计满足某条件的整数个数

小结（实战流程模板）

遇到一道新题，用下面的流程套一遍：

试着用暴力递归写出状态转移（明确子问题）。
判断是否存在重叠子问题 & 最优子结构（可以用 DP）。
明确 dp 含义、转移和 base case。
先写递归 + 记忆化验证正确性，再改成迭代表格（若需要）。
考虑时间/空间复杂度，做常见优化（滚动数组/前缀/单调队列等）。
若需要恢复解，额外记录选择信息并回溯。

贡献者

bbhou