动态规划

动态规划

动态规划是竞赛中分值最高的专题之一。共 20 个模板。

← 返回模板库

7.101背包

每件物品只能选一次，状态压缩为一维

O(n × W)

7.2完全背包

每件物品可选无限次，正序遍历容量

O(n × W)

7.3多重背包

每件物品有限个，二进制拆分优化

O(n × W × log C)

7.4分组背包

每组物品只能选一个，组间顺序遍历

O(V × Σn)

7.5最长上升子序列（LIS）

贪心 + 二分优化到 O(n log n)

O(n log n)

7.6最长公共子序列（LCS）

经典二维 DP，逐字符比较

O(n × m)

7.7编辑距离

增删改三种操作的最小代价

O(n × m)

7.8数字三角形

入门经典，自底向上求最大路径和

O(n²)

7.9最大子段和（Kadane）

动态规划求连续子数组最大和

O(n)

7.10最长回文子序列

区间 DP，dp[i][j] 表示 s[i..j] 的最长回文子序列

O(n²)

7.11石子合并

区间 DP 典型，相邻堆合并的最小代价

O(n³)

7.12戳气球

区间 DP，逆向思维求最大得分

O(n³)

7.13树形 DP - 没有上司的舞会

在树上做 DP，选/不选两种状态

O(n)

7.14树形背包

树上背包问题，子树合并

O(n × W)

7.15状压 DP - 旅行商

用二进制状态表示已访问的城市集合

O(2^n × n²)

7.16数位 DP - 统计方案数

按位枚举，限制前缀

O(位数 × 状态数 × 10)

7.17数位 DP - 不含特定数字

统计区间内不含某数字的数的个数

O(位数 × 10)

7.18概率/期望 DP

状态转移涉及概率与期望

视问题而定

7.19线性 DP - 方格取数

从左上到右下，路径不能重复

O(n³)

7.20DP 优化 - 单调队列优化

利用单调队列优化滑动窗口最值转移

O(n)