动态规划算法

动态规划是一种将复杂问题分解为更小的子问题并通过缓存子问题的解来避免重复计算的算法设计方法。它适用于具有重叠子问题和最优子结构性质的问题。动态规划通常用于优化问题，目的是通过构建递归关系和记忆化中间结果，找到全局最优解。

核心思想

动态规划的核心思想是将一个复杂的问题分解为若干个子问题，然后通过递推的方式逐步解决这些子问题。它的基本步骤如下：

1. 定义状态：确定问题的状态，也就是用哪些变量来描述当前子问题的状态。
2. 状态转移方程：找到子问题之间的递推关系（即状态转移方程），描述如何从已解决的子问题得到当前问题的解。
3. 边界条件：确定初始状态的值，通常是最小规模的问题的解。
4. 计算顺序：根据状态转移方程的依赖关系，从小到大计算每个子问题的解。

动态规划常用来解决最优化问题，如最短路径问题、最大子序列和问题、背包问题等。

动态规划的特性

1. 重叠子问题：动态规划问题通常具有重叠子问题，即原问题可以分解成若干个相同的子问题。不同的子问题可能会在递归求解中被重复计算。如果使用简单的递归方法，会导致大量的重复计算，因此通过记忆化技术（如数组或表）存储子问题的解，可以避免重复计算。

2. 最优子结构：如果问题的最优解可以由其子问题的最优解构造而成，称为最优子结构。例如，求解最短路径时，如果最短路径经过某个点，那么从该点到终点的子路径也一定是最短路径。

动态规划的两种实现方式

1. 自顶向下（记忆化搜索）：使用递归的方式自顶向下解决问题，同时将子问题的解存储在数组或哈希表中（称为“记忆化”），以便下次遇到相同的子问题时直接返回之前计算的结果，而不是重新计算。

2. 自底向上（迭代法）：先解决最简单的子问题，然后通过迭代的方式解决规模逐渐增大的问题。自底向上通常表现为使用一个数组或表，按照状态转移方程逐步填充表中的值。

动态规划的经典例题

1. 斐波那契数列

这是动态规划最简单的例子，斐波那契数列的递归公式为：
[
F(n) = F(n-1) + F(n-2)
]
使用动态规划，可以避免递归的重复计算。

状态定义：令 dp[i] 表示斐波那契数列第 i 项的值。

状态转移方程：
[
dp[i] = dp[i-1] + dp[i-2]
]

边界条件：
[
dp[0] = 0, \ dp[1] = 1
]

自底向上代码实现：

1
2
3
4
5
6
7
8
9
10

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    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]

2. 背包问题

背包问题是经典的动态规划问题，描述如下：有一个背包容量为 W，有 n 个物品，每个物品有重量 w_i 和价值 v_i，问如何选择物品装入背包，使得装入背包的物品总价值最大。

状态定义：dp[i][j] 表示前 i 个物品在背包容量为 j 时的最大价值。

状态转移方程：
[
dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)
]
如果不选择第 i 个物品，则 dp[i][j] = dp[i-1][j]；如果选择，则 dp[i][j] = dp[i-1][j-w_i] + v_i。

边界条件：dp[0][j] = 0（没有物品时最大价值为0）。

3. 最长公共子序列（LCS）

给定两个序列，求它们的最长公共子序列。其状态转移方程为：

[
dp[i][j] =
\begin{cases}
dp[i-1][j-1] + 1, & \text{if } s1[i] = s2[j] \
\max(dp[i-1][j], dp[i][j-1]), & \text{if } s1[i] \neq s2[j]
\end{cases}
]

总结

动态规划通过记忆化子问题的解，可以极大地提高算法的效率。掌握动态规划的关键在于能识别问题的重叠子问题和最优子结构，并合理地定义状态和状态转移方程。