Dynamic Programming

Exisfar2025-04-202025-07-21

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

Dynamic Programming

DP的有几种求解方式？

动态规划的编程求解方式主要有以下 4 种经典实现形式，每种各有特点和适用场景：

1. 自顶向下递归 + 备忘录（Top-Down with Memoization）

实现方式：递归调用 + 存储中间结果
核心技巧：@cache / @lru_cache 装饰器或手动建字典

示例（斐波那契数列）：

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)

优点：代码直观，接近数学定义
缺点：递归深度限制，函数调用开销

2. 自底向上迭代（Bottom-Up Tabulation）

实现方式：从基础case逐步填充DP表
典型结构：数组/矩阵 + 循环嵌套

示例（0-1背包问题）：

def knapsack(values, weights, capacity):
    n = len(values)
    dp = [[0]*(capacity+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for w in range(1, capacity+1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacity]

优点：无递归栈溢出风险，空间可优化
缺点：需确定计算顺序

3. 状态压缩（Space Optimization）

适用场景：DP表仅依赖前一行/前几项时
实现技巧：滚动数组/变量复用

示例（斐波那契数列优化）：

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

优化效果：将O(n²)空间降为O(n)或O(1)

4. 分治法 + 记忆化（Divide & Conquer）

特殊场景：区间DP（如矩阵链乘法）
典型结构：递归分割问题 + 合并子解

示例（矩阵链乘最小代价）：

@cache
def matrix_chain_mul(i, j):
    if i == j: return 0
    return min(
        matrix_chain_mul(i, k) + matrix_chain_mul(k+1, j)
        + p[i-1]*p[k]*p[j] for k in range(i, j)
    )

方法选择指南：

方法	适用场景	空间复杂度
自顶向下	树形结构问题（如二叉树DP）	O(递归深度)
自底向上	常规线性/二维DP	O(n²)或O(n)
状态压缩	仅需前驱状态的问题	O(1)或O(n)
分治法	区间分割问题	O(n²)

必须使用回溯算法而无法用DP解决的问题

1. 需要枚举所有可能解（而不仅仅是优化解）

动态规划通常用于求解最优解（如最大值、最小值、最短路径等），但无法直接输出所有可能的解。
典型问题：
• 全排列（Permutations）：如 [1,2,3] 的所有排列组合。

• DP 无法直接生成所有排列，但回溯可以通过交换元素穷举。

• 子集（Subsets）：如 [1,2] 的子集 [], [1], [2], [1,2]。

• DP 可以计算子集的数量（2^n），但无法输出具体子集。

原因：DP 的状态转移会合并重叠子问题，丢失具体路径信息。

2. 问题具有不可分解的约束条件

当问题的约束条件无法通过状态转移方程表达时，DP 失效。
典型问题：
• N皇后问题：在棋盘上放置皇后，要求互不攻击。
• 约束条件（行列、对角线上无冲突）无法用 DP 状态简单表示。
• 回溯可以逐行尝试并回溯冲突的位置。
• 数独求解：填充数字满足行列和子网格约束。
• DP 难以处理局部填数对全局的影响。

原因：DP 要求问题具有最优子结构，而此类约束是全局的、非累加的。

3. 解空间是隐式图（非结构化状态）

当问题的状态转移无法显式定义时，回溯的深度优先搜索（DFS）更灵活。
典型问题：
• 图的哈密尔顿路径：访问所有节点恰好一次的路径。
• DP 需要预先定义状态（如 dp[mask][u] 表示已访问节点集合 mask 和当前位置 u），但实现复杂且效率可能低于回溯。
• 正则表达式匹配（穷举所有匹配方式）：如 a*a 匹配 aaa 的所有可能方式。

原因：DP 需要明确的状态定义，而回溯可以通过递归隐式探索解空间。

4. 动态规划的局限性对比回溯

特性	动态规划	回溯
目标	优化问题（单解）	枚举问题（多解/所有解）
约束处理	需可分解为子问题	可处理任意约束
状态表示	需显式定义状态转移方程	隐式通过递归探索
时间复杂度	通常多项式（如 O(n²)）	通常指数级（如 O(2^n)）

5. 为什么不能强行用 DP 解决上述问题？

• 状态爆炸：例如在 N皇后问题中，棋盘状态需要记录所有已放置皇后的位置，状态空间呈指数增长。

• 信息丢失：DP 会合并子问题的解，但回溯需要保留完整路径（如排列问题中每个数字的选择顺序）。

总结

✅ 必须用回溯的问题：

需要输出所有解（非优化解）。
约束条件无法分解为子问题。
解空间是隐式或非结构化的。

🚫 DP 的适用场景：最优解问题、状态可明确划分、具有重叠子问题。

经典示例：
• 能用 DP：斐波那契数列、背包问题、最短路径。
• 必须回溯：全排列、N皇后、数独、图的哈密尔顿路径。

分治法和动态规划的区别？

它们都是将问题分解为子问题来解决。

分治法：

将问题分解为若干个独立的子问题，递归地求解每个子问题，然后将子问题的解合并为原问题的解。
分治法通常不关心子问题是否重复，即使子问题重复，也会重新计算。

动态规划：

将问题分解为若干个重叠的子问题，通过记忆化或表格化存储子问题的解，避免重复计算。
动态规划的核心是最优子结构和重复子问题。

适用场景

分治法：

• 子问题独立，没有重叠。
• 问题的分解和合并过程相对简单。
• 典型问题：
• 归并排序（Merge Sort）
• 快速排序（Quick Sort）
• 二分查找（Binary Search）
• 大整数乘法（Karatsuba Algorithm）

动态规划：

• 子问题重叠，且具有最优子结构。
• 问题的解可以通过子问题的最优解构造。
• 典型问题：
• 背包问题（Knapsack Problem）
• 最长公共子序列（Longest Common Subsequence, LCS）
• 最短路径问题（如 Floyd-Warshall 算法）
• 斐波那契数列（Fibonacci Sequence）

实现方式

分治法：

• 通常使用递归实现。
• 不需要存储子问题的解，因为子问题是独立的。
• 示例：归并排序

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

动态规划：

可以使用递归+记忆化（自顶向下）或迭代+表格化（自底向上）实现。
需要存储子问题的解，避免重复计算。
示例：斐波那契数列

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

时间复杂度

分治法：

• 时间复杂度取决于子问题的数量和合并的复杂度。
• 示例：
• 归并排序：O(n log n)
• 快速排序：平均 O(n log n)，最坏 O(n^2)

动态规划：

• 时间复杂度取决于子问题的数量和每个子问题的计算复杂度。
• 示例：
• 背包问题：O(nW)，其中 n 是物品数量，W 是背包容量。
• 斐波那契数列：O(n)

空间复杂度

分治法：

• 空间复杂度通常较低，因为不需要存储子问题的解。
• 示例：
• 归并排序：O(n)（用于合并过程）
• 快速排序：O(log n)（递归栈）

动态规划：

• 空间复杂度较高，因为需要存储子问题的解。
• 示例：
• 背包问题：O(nW)
• 斐波那契数列：O(n)

优缺点

分治法：

• 优点：
• 实现简单，逻辑清晰。
• 适用于子问题独立的问题。
• 缺点：
• 对于子问题重叠的问题，效率较低。

动态规划：

• 优点：
• 通过存储子问题的解，避免重复计算，提高效率。
• 适用于具有最优子结构和重叠子问题的问题。
• 缺点：
• 实现复杂，需要设计状态和状态转移方程。
• 空间复杂度较高。

典型问题对比

问题	分治法	动态规划
归并排序	适用	不适用
快速排序	适用	不适用
斐波那契数列	不适用（效率低）	适用
背包问题	不适用	适用
最长公共子序列（LCS）	不适用	适用
大整数乘法	适用	不适用

什么场景不适合用DP？

动态规划（Dynamic Programming, DP）是一种解决优化问题的强大技术，特别适用于具有重叠子问题和最优子结构性质的问题。然而，并不是所有问题都适合使用动态规划。以下是一些不适合使用动态规划的场景：

1. 问题没有最优子结构

动态规划的核心思想是将问题分解为子问题，并通过子问题的最优解来构造原问题的最优解。如果问题不具备最优子结构（即原问题的最优解不能由其子问题的最优解构造），则动态规划不适用。

例子：
• 最长路径问题：在图中寻找最长路径。这个问题不具备最优子结构，因为子问题的最优解不能直接用于构造原问题的最优解。

2. 子问题没有重叠

动态规划的优势在于通过记忆化或表格化避免重复计算子问题。如果问题的子问题没有重叠，则动态规划无法发挥其优势，反而可能增加额外的空间和时间开销。

例子：
• 归并排序：归并排序的每个子问题都是独立的，没有重叠，因此不适合用动态规划。

3. 问题规模过大

动态规划通常需要存储子问题的解，这可能导致空间复杂度过高。如果问题的规模非常大，动态规划可能会超出内存限制。

例子：
• 大规模背包问题：如果背包容量非常大（例如 10^9），动态规划的空间复杂度会变得不可行。

4. 问题不适合分解为子问题

如果问题无法自然地分解为子问题，或者子问题的解无法有效地组合成原问题的解，则动态规划不适用。

例子：
• 模拟类问题：如模拟物理系统或游戏规则，这类问题通常需要逐步迭代，而不是通过子问题求解。

5. 问题需要精确解，但动态规划只能提供近似解

某些动态规划算法（如基于贪心策略的 DP）只能提供近似解，而不是精确解。如果问题需要精确解，则动态规划可能不适用。

例子：
• 旅行商问题（TSP）：虽然可以用动态规划解决，但它的时间复杂度为 O(n^2 * 2^n)，对于大规模问题不实用。

6. 问题有更高效的算法

如果问题存在更高效的算法（如贪心算法、分治法、数学公式等），则不需要使用动态规划。

例子：
• 斐波那契数列：虽然可以用动态规划解决，但使用矩阵快速幂或通项公式可以在 O(log n) 时间内解决。

7. 问题不适合记忆化

如果问题的状态空间非常复杂，或者状态难以定义和存储，则动态规划的记忆化方法可能不适用。

例子：
• 连续状态问题：如某些优化问题，状态是连续的（例如实数范围），难以用表格存储。

总结

动态规划适合解决具有重叠子问题和最优子结构的优化问题，但在以下场景中可能不适用：

问题没有最优子结构。
子问题没有重叠。
问题规模过大，超出内存限制。
问题无法分解为子问题。
需要精确解但动态规划只能提供近似解。
存在更高效的算法。
状态空间复杂，难以记忆化。

在实际应用中，需要根据问题的特点选择合适的算法。