Dynamic Programming

Exisfar2025-04-202025-04-26

Dynamic Programming

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

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

分治法：

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

动态规划：

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

适用场景

分治法：

• 子问题独立，没有重叠。
• 问题的分解和合并过程相对简单。
• 典型问题：
• 归并排序（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. 问题不适合记忆化

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

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

总结

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

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

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