动态规划 | ZaynusX的博客

动态规划（Dynamic Programming，简称DP）是一种用于解决最优化问题的算法思想，通常用于具有重叠子问题和最优子结构性质的问题。它的核心思想是通过将问题分解为子问题，并保存子问题的解（避免重复计算），从而高效地求解原问题。

动态规划的核心思想

分解问题：
- 将原问题分解为若干子问题，子问题的解可以组合成原问题的解。
保存子问题的解：
- 使用表格（通常是数组或矩阵）保存子问题的解，避免重复计算。
递推求解：
- 通过子问题的解逐步推导出原问题的解。

动态规划的两个关键性质

最优子结构：
- 原问题的最优解可以通过子问题的最优解推导出来。
- 例如，最短路径问题中，从A到B的最短路径可以通过A到中间点的最短路径推导出来。
重叠子问题：
- 在求解过程中，子问题会被多次重复计算。
- 例如，斐波那契数列中，fib(5)的计算需要重复计算fib(3)和fib(4)。

动态规划的步骤

定义状态：
- 用状态表示问题的子问题，通常用一个或多个变量表示。
- 例如，dp[i]表示第i个问题的解。
状态转移方程：
- 描述子问题之间的关系，即如何从已知子问题的解推导出当前问题的解。
- 例如，斐波那契数列的状态转移方程为：dp[i] = dp[i-1] + dp[i-2]。
初始化：
- 确定初始状态的值，通常是最小的子问题的解。
- 例如，斐波那契数列中，dp[0] = 0，dp[1] = 1。
递推求解：
- 根据状态转移方程，逐步计算所有子问题的解。
返回结果：
- 最终结果通常存储在某个状态中，例如dp[n]。

动态规划的两种实现方式

自顶向下（记忆化搜索）：
- 从原问题开始，递归地分解为子问题，同时保存子问题的解。
- 使用递归实现，通常配合备忘录（Memoization）来避免重复计算。
- 适合子问题数量较少的情况。
- 示例：斐波那契数列的递归解法。
自底向上（迭代法）：
- 从最小的子问题开始，逐步求解更大的子问题，直到解决原问题。
- 使用循环实现，通常用数组或矩阵保存子问题的解。
- 适合子问题数量较多的情况。
- 示例：斐波那契数列的迭代解法。

动态规划的经典问题

斐波那契数列：
- 状态转移方程：dp[i] = dp[i-1] + dp[i-2]。
- 初始条件：dp[0] = 0，dp[1] = 1。
背包问题：
- 状态定义：dp[i][j]表示前i个物品在容量为j的背包中的最大价值。
- 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。
最长公共子序列（LCS）：
- 状态定义：dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。
- 状态转移方程：
  - 如果A[i] == B[j]，则dp[i][j] = dp[i-1][j-1] + 1。
  - 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最短路径问题：
- 状态定义：dp[i][j]表示从起点到(i, j)的最短路径。
- 状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j]。

动态规划的代码框架（以斐波那契数列为例）

自顶向下（记忆化搜索）

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]

自底向上（迭代法）

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

总结

动态规划是一种强大的算法思想，适用于具有最优子结构和重叠子问题性质的问题。通过定义状态、建立状态转移方程、初始化边界条件，并采用自顶向下或自底向上的方法求解，可以高效地解决许多复杂问题。