动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决。动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子阶段，按顺序求解子阶段。与分治不同的是，在动态规划过程中，前一子问题的解，为后一子问题的求解提供了有用的信息，也就是说前后阶段的问题求解存在依赖关系。在求解任一子问题时，通过决策保留那些有可能达到最优的局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
一、动态规划问题的特征
最优化原理（最优子结构）： 最优子结构是动态规划能够应用的基础。最优子结构意味着一个问题的最优解可以通过其子问题的最优解来构造。如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构。换句话说，当前问题的最优解可以通过对较小子问题的最优解进行组合而得出。
例子：在背包问题中，背包总容量为 \(W\)，物品集合为 \(n\) 个。我们可以将这个问题划分为两个子问题：是否选择某个物品 \(i\)。如果选择该物品，问题就转化为容量为 \(W - w_i\) 的最优解；如果不选择，问题则变为容量为 \(W\) 时剩下 \(n - 1\) 个物品的最优解。两个子问题的最优解决定了整体问题的最优解。
无后效性： 无后效性指的是某阶段的状态一旦确定，就不受这个状态以后决策的影响。这意味着某个状态所涉及的决策只依赖于当前的状态和前面的决策，而不会受到将来决策的影响。通俗地讲，一旦状态 \(x_k\) 被选定，那么系统从当前阶段 \(k\) 开始的后续行为只与 \(x_k\) 相关，与此前的决策无关。
例子：在路径规划问题中，选择到达某一个点 \(A\) 的最短路径不需要考虑之前是通过哪条路径到达的，只需要知道从点 \(A\) 到终点的距离以及经过 \(A\) 的最短路径即可。因此，当前阶段的决策只取决于当前状态，而不会依赖之前如何走到这个状态。
重叠子问题： 重叠子问题指的是在递归求解的过程中，不同的阶段可能会遇到相同的子问题。为了避免重复计算，可以将这些子问题的结果保存起来，以供后续使用，从而降低算法复杂度。相比于贪心算法或分治法，动态规划的优势在于重叠子问题的存在。
例子：在斐波那契数列求解问题中，计算 \(F(n)\) 时需要计算 \(F(n-1)\) 和 \(F(n-2)\)，但是在计算 \(F(n-1)\) 时又会再次计算 \(F(n-2)\)，这就是重叠子问题。如果不进行保存，计算过程中会出现大量的重复计算。通过动态规划保存这些中间结果，可以极大地提高效率。
二、动态规划求解的步骤
划分阶段： 将问题按照一定的顺序划分为若干个阶段，通常每个阶段表示某种子问题。划分阶段的原则是确保子问题之间可以递推，并且后续的决策只依赖当前的状态。
选择状态变量： 选择合适的状态变量来描述每个阶段的状态。状态变量要尽量全面地描述当前的情况，并确保能够通过状态转移方程递推。
建立状态转移方程： 确定状态之间的递推关系，即状态转移方程。状态转移方程是动态规划的核心，明确了如何从一个状态过渡到另一个状态。
定义边界条件： 为了递推求解，必须定义初始状态的解，通常是最小阶段的解。边界条件为动态规划的起始点，递推从这里开始。
自底向上求解： 动态规划采用自底向上的方式求解，即从最小的子问题开始递推，逐步解决更大的问题。通过存储子问题的解，避免重复计算，提高效率。
输出最优解： 最终，动态规划输出的是最优值函数的值，即问题的最优解。
三、动态规划问题求解
3.1 青蛙跳阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。
假设青蛙跳上第\(n\)级台阶，有两种方式：从第\(n-1\)级跳上来；从第\(n-2\)级跳上来。因此，要跳上第\(n\)级台阶的总跳法数等于跳上第\(n-1\)级台阶的跳法数加上跳上第\(n-2\)级台阶的跳法数。动态规划建模过程如下：
- 阶段（Stage）：每一阶段对应跳上某一级台阶。共有\(n\)阶台阶，从 1 到\(n\)阶。
- 状态（State）：状态可以用\(f(n)\)表示跳上第\(n\)级台阶的总跳法数。
- 状态转移方程（State Transition Equation）：如上分析，状态转移方程为：$$f(n) = f(n-1) + f(n-2)$$
- 边界条件：
- 跳上第 1 级台阶时，只有一种跳法，即\(f(1) = 1\)；
- 跳上第 2 级台阶时，有两种跳法，即\(f(2) = 2\)（可以一次跳 1 级，也可以一次跳 2 级）。
- 根据状态转移方程和边界条件，递推方程为：$$f(n) = f(n-1) + f(n-2), \quad \text{for } n \geq 3$$
def frog_jumps(n):
# 边界条件
if n == 1:
return 1
elif n == 2:
return 2
# 动态规划数组
dp = [0] * (n + 1)
dp[1] = 1 # 跳上第 1 级台阶只有 1 种方法
dp[2] = 2 # 跳上第 2 级台阶有 2 种方法
# 递推求解每一级台阶的跳法数
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 求解青蛙跳上 10 级台阶的跳法总数
n = 10
result = frog_jumps(n)
print(f"跳上 {n} 级台阶的总跳法数为：{result}")
3.2 矩形最小路径和
矩形最小路径和问题是经典的动态规划问题。题目通常要求我们从一个矩形网格的左上角出发，经过某些路径到达右下角，使得经过的路径上的数值和最小。只能向下或者向右移动。假设一个\(4 \times 5\)的网格，其每个格子中的数值表示路径的权重，网格数据如下：
[1, 3, 1, 4, 2]
[1, 5, 1, 2, 3]
[4, 2, 1, 7, 2]
[1, 2, 3, 1, 1]
设 \(dp[i][j]\) 表示到达坐标 \((i, j)\) 的最小路径和。
状态转移方程
- 若 \(i == 0\)，则 \(dp[i][j] = dp[i][j-1] + grid[i][j]\)（只能从左边过来）
- 若 \(j == 0\)，则 \(dp[i][j] = dp[i-1][j] + grid[i][j]\)（只能从上面过来）
- 否则，\(dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]\)（可以从上方或左方过来，取较小者）
初始状态：\(dp[0][0] = grid[0][0]\)
目标：计算出 \(dp[3][4]\)，即从左上角到右下角的最小路径和。
def minPathSumWithTrace(grid):
rows = len(grid)
cols = len(grid[0])
# 创建 dp 数组和路径数组
dp = [[0 for _ in range(cols)] for _ in range(rows)]
path = [[None for _ in range(cols)] for _ in range(rows)] # 用于记录路径
# 初始化起点
dp[0][0] = grid[0][0]
path[0][0] = (-1, -1) # 用于标记起点
# 初始化第一行
for j in range(1, cols):
dp[0][j] = dp[0][j-1] + grid[0][j]
path[0][j] = (0, j-1) # 只能从左边过来
# 初始化第一列
for i in range(1, rows):
dp[i][0] = dp[i-1][0] + grid[i][0]
path[i][0] = (i-1, 0) # 只能从上边过来
# 填充 dp 数组
for i in range(1, rows):
for j in range(1, cols):
# 比较从上方和左方的路径，选择最小的
if dp[i-1][j] < dp[i][j-1]:
dp[i][j] = dp[i-1][j] + grid[i][j]
path[i][j] = (i-1, j) # 记录从上方来的路径
else:
dp[i][j] = dp[i][j-1] + grid[i][j]
path[i][j] = (i, j-1) # 记录从左方来的路径
# 回溯路径
min_path = []
i, j = rows - 1, cols - 1 # 从右下角开始
while (i, j) != (-1, -1): # 一直到起点
min_path.append((i, j))
i, j = path[i][j]
# 返回最小路径和以及路径（逆序后输出路径）
return dp[rows-1][cols-1], min_path[::-1] # 逆序输出路径
# 测试数据
grid = [
[1, 3, 1, 4, 2],
[1, 5, 1, 2, 3],
[4, 2, 1, 7, 2],
[1, 2, 3, 1, 1]
]
# 调用函数，输出最小路径和和路径
result, min_path = minPathSumWithTrace(grid)
print("矩形最小路径和为:", result)
print("最小路径为:", min_path)
3.3 数字三角形的最大路径和
在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于 1 小于等于 100，数字为 0 - 99。
如果当前在第 \(i\) 行的第 \(j\) 个元素，那么它的最大路径和可以通过下面的公式计算：$$f(i, j) = a(i, j) + \max(f(i+1, j), f(i+1, j+1))$$
其中：
- \(f(i, j)\) 表示从位置 \((i, j)\) 开始到达底部的最大路径和。
- \(a(i, j)\) 是当前的数字。
def max_path_sum_with_trace(triangle):
# 行数
n = len(triangle)
# 初始化路径数组，记录每个点的最佳选择（0表示向左下，1表示向右下）
path = [[-1] * len(row) for row in triangle]
# 建立一个副本用于存储最大路径和，不改变原三角形的值
dp = [row[:] for row in triangle]
# 从倒数第二层开始向上计算最大路径和
for i in range(n - 2, -1, -1):
for j in range(len(dp[i])):
# 动态规划方程，选择较大的那个方向
if dp[i + 1][j] > dp[i + 1][j + 1]:
dp[i][j] += dp[i + 1][j]
path[i][j] = 0 # 选择左下
else:
dp[i][j] += dp[i + 1][j + 1]
path[i][j] = 1 # 选择右下
# 计算最大路径和
max_sum = dp[0][0]
# 追踪路径，记录经过的数字
j = 0 # 从顶部开始
optimal_path = [triangle[0][0]] # 记录路径上的数字
for i in range(1, n):
if path[i - 1][j] == 0:
j = j # 左下
else:
j = j + 1 # 右下
optimal_path.append(triangle[i][j]) # 将选择的数字加入路径
return max_sum, optimal_path
# 示例三角形，行数为5
triangle = [
[7],
[3, 8],
[8, 1, 0],
[2, 7, 4, 4],
[4, 5, 2, 6, 5]
]
# 调用函数
max_sum, path = max_path_sum_with_trace(triangle)
print("最大路径和:", max_sum)
print("经过的数字路径:", path)
总结
动态规划是一种用于解决具有最优子结构和重叠子问题的优化算法。其核心思想是通过将复杂问题分解为若干个相互关联的子问题，逐步求解并保存每个子问题的结果，避免重复计算，最终得到问题的最优解。动态规划最优子结构意味着问题的整体最优解可以通过子问题的最优解构成，确保递推求解的可行性；无后效性保证每个阶段的状态一旦确定，不受未来决策影响，只依赖当前的状态和之前的决策；重叠子问题则是动态规划效率的源泉，通过保存子问题的结果，可以避免多次计算同一子问题。动态规划的求解步骤包括：划分阶段、定义状态变量、构建状态转移方程、设定初始条件，并自底向上递推求解。常见应用领域包括背包问题、路径规划、股票买卖等。总的来说，动态规划是解决复杂优化问题的高效方法，尤其适用于具有递归结构的问题。
