本文档涵盖了仓库中的动态规划算法和实现，包括经典的优化问题、序列处理算法和高级应用。对于使用类似优化原则的图算法，请参阅图算法与网络分析。对于不使用动态规划的字符串处理算法，请参阅字符串处理与模式匹配。
动态规划通过将优化问题分解为重叠子问题并存储结果以避免重复计算来解决问题。该仓库在各种问题领域实现了记忆化（自顶向下）和递推（自底向上）两种方法。
来源：dynamic_programming/rod_cutting.py14-174 dynamic_programming/combination_sum_iv.py45-72
| 问题类型 | 经典示例 | 空间复杂度 | 优化技术 |
|---|---|---|---|
| 线性动态规划 | longest_increasing_subsequence(), max_product_subarray() | O(n) | 滚动变量法 |
| 二维网格动态规划 | longest_common_subsequence(), knapsack() | O(m×n) | 行空间优化 |
| 区间动态规划 | matrix_chain_multiply() | O(n²) | 对角线填充 |
| 字符串动态规划 | all_construct(), dp_match() | O(m×n) | 模式优化 |
来源：dynamic_programming/longest_increasing_subsequence.py19-61 dynamic_programming/longest_common_subsequence.py9-82 dynamic_programming/matrix_chain_multiplication.py54-96
该仓库提供了具有不同优化目标的全面背包问题实现。
来源：dynamic_programming/knapsack.py29-39 dynamic_programming/knapsack.py10-26 dynamic_programming/knapsack.py42-100
longest_common_subsequence()函数实现了经典的字符串比对算法，包括长度计算和序列重构。
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + match)来源：dynamic_programming/longest_common_subsequence.py59-82
两种实现提供了不同的时间复杂度权衡。
| 实现 | 时间复杂度 | 空间复杂度 | 算法 |
|---|---|---|---|
longest_subsequence() | O(2^n) | O(n) | 带有剪枝的递归 |
longest_increasing_subsequence_length() | O(n log n) | O(n) | 二分查找优化 |
来源：dynamic_programming/longest_increasing_subsequence.py19-61 dynamic_programming/longest_increasing_subsequence_o_nlogn.py20-49
matrix_chain_multiply()函数解决了最优括号化问题。
来源：dynamic_programming/matrix_chain_multiplication.py86-94
viterbi()函数实现了最可能状态序列算法。
observations_space, states_space, 概率字典来源：dynamic_programming/viterbi.py4-176
dp_match()函数提供了 O(m×n) 的正则表达式匹配，支持.（任意字符）和*（零个或多个）操作符。
来源：dynamic_programming/regex_match.py82-89
all_construct()函数找到从词库构造目标字符串的所有方式。
table[i]包含构造target[:i]的所有方式[word, *way] for way in table[i]来源：dynamic_programming/all_construct.py22-48
许多二维动态规划问题可以优化为使用 O(min(m,n)) 空间。
| 算法 | 原始空间 | 优化空间 | 技术 |
|---|---|---|---|
| LCS | O(m×n) | O(min(m,n)) | 双行技术 |
| 背包问题 | O(n×W) | O(W) | 滚动数组 |
| LIS | O(n²) | O(n) | 二分查找 |
来源：dynamic_programming/rod_cutting.py14-53 dynamic_programming/longest_increasing_subsequence_o_nlogn.py20-49
虽然并非严格意义上的动态规划，但线段树具有相似的递归分解原理，并用于动态规划的优化。
build(1, 0, N-1)自底向上构建树来源：data_structures/binary_tree/segment_tree.py38-97 data_structures/binary_tree/non_recursive_segment_tree.py47-116
马拉车算法（Manacher's algorithm）用于回文检测，展示了类似动态规划的优化。
k = min(length[left + right - j] // 2, right - j + 1)