动态规划（Dynamic Programming）

概述

动态规划是一种通用的算法设计技术，用于解决由具有重叠子问题的递归定义的问题。1950年代，美国数学家理查德·贝尔曼（Richard Bellman）发明了动态规划以解决优化问题。动态规划并不是计算机编程，而是指随时间进行的计划。

动态规划的主要思想

建立一个递归关系，将较大实例的解与一些较小实例的解联系起来。
只解决较小的实例一次。
将解记录在表中。
从表中提取初始实例的解。

示例：计算斐波那契数列

斐波那契数列定义

\begin{aligned} F(n) &= F(n - 1) + F(n - 2) \\ F(0) &= 0 \\ F(1) &= 1 \end{aligned}

自顶向下计算（递归）

效率类：指数级别
$A_n \in \Theta(\phi^n)$

自底向上计算（表填充）

预先计算所有可能需要的子问题
经典的动态规划方法

顶端向下（记忆化）

按需计算，但记住使用内存函数的解

示例：计算斐波那契数

自底向上迭代并记录结果

效率类：线性
$A_n \in \Theta(n)$

int fib(int n) {
    int f[n+1];
    int i;
    f[0] = 0;   
    f[1] = 1;
    for (i = 2; i <= n; i++) 
        f[i] = f[i-1] + f[i-2]; 
    return f[n]; 
}

动态规划的应用

动态规划广泛应用于以下领域：

生物信息学
控制理论
信息论
运筹学
计算机科学：理论、图形学、人工智能、系统等

一些动态规划应用实例

零钱兑换问题
0-1 背包问题
生产线调度
最长公共子序列问题
矩阵链乘法
全源最短路径问题（Floyd算法）

算法范例

贪心算法（Greedy）：逐步构建解，局部优化某些标准。
分治算法（Divide-and-conquer）：将问题分解为独立的子问题，解决每个子问题，并将子问题的解组合成原问题的解。
动态规划（Dynamic programming）：将问题分解为一系列重叠的子问题，并构建更大子问题的解。

硬币行问题的动态规划解法确实可以用递推公式来描述。通过动态规划，可以确定从n个硬币中挑选最大金额且不能挑选相邻的硬币的最优解。

递推公式

设 $F(n)$ 为从前n个硬币中能挑选的最大金额，那么递推公式可以表示如下：

F(n) = \max\{c_n + F(n-2), F(n-1)\}, \text{for } n > 1

其中：

$c_n + F(n-2)$ 表示选择第n个硬币，那么前一个可选择的硬币就是第n-2个，最大金额就是当前硬币的值加上前n-2个硬币能挑选的最大金额。
$F(n-1)$ 表示不选择第n个硬币，那么最大金额就是前n-1个硬币能挑选的最大金额。

边界条件

$F(0) = 0$ : 当没有硬币时，能挑选的最大金额为0。
$F(1) = c_1$ : 当只有一个硬币时，能挑选的最大金额就是这个硬币的值。

动态规划过程

初始化边界条件： $F(0) = 0$ , $F(1) = c_1$ 。
递推计算 $F(n)$ ：

F(n) = \max\{c_n + F(n-2), F(n-1)\}

举例

假设有一行硬币，其值分别为 $[c_1, c_2, c_3, c_4, c_5]$ ，按照动态规划过程：

初始化： $F(0) = 0$ , $F(1) = c_1$
计算 $F(2)$ ： $F(2) = \max\{c_2, c_1\}$
计算 $F(3)$ ： $F(3) = \max\{c_3 + F(1), F(2)\} = \max\{c_3 + c_1, F(2)\}$
计算 $F(4)$ ： $F(4) = \max\{c_4 + F(2), F(3)\}$
计算 $F(5)$ ： $F(5) = \max\{c_5 + F(3), F(4)\}$

这样一步步递推，就可以得到从n个硬币中能挑选的最大金额。

递推公式总结

F(n) = \begin{cases} 0 & \text{if } n = 0 \\ c_1 & \text{if } n = 1 \\ \max\{c_n + F(n-2), F(n-1)\} & \text{if } n > 1 \end{cases}

通过这个递推公式，可以有效地解决硬币行问题，找到能够挑选的最大金额。

零钱兑换问题

问题描述

给定无限数量的硬币，面值分别为 $d1 > d2 > \ldots > dm$ ，用最少的硬币凑出金额n。

动态规划解法

设 $F(n)$ 为凑出金额n的最少硬币数。

F(n) = \min_{j:n \geq d_j} \{F(n - d_j) + 1\} \text{ for } n > 0

F(0) = 0

示例

金额n=6，硬币面值集合为{1,3,4}。最小硬币集合为（3, 3）。

背包问题

问题描述

给定n个物品和一个“背包”，每个物品i的重量为 $w_i > 0$ ，价值为 $v_i > 0$ ，背包的容量为 $W$ 。目标是填满背包，使总价值最大。

动态规划解法

设 $V(i, j)$ 为从物品1到i中选出重量不超过j的最大价值。

如果不选择物品i，则 $V(i, j) = V(i - 1, j)$
如果选择物品i，则 $(V(i, j) = \max\{V(i - 1, j), v_i + V(i - 1, j - w_i)\}$

递推公式

V(0, j) = 0 \text{ for } j \geq 0

V(i, 0) = 0 \text{ for } i \geq 0

V(i, j) = \begin{cases} V(i - 1, j) & \text{if } j - w_i < 0 \\ \max\{V(i - 1, j), v_i + V(i - 1, j - w_i)\} & \text{if } j - w_i \geq 0 \end{cases}

示例

给定物品及其价值和重量如下表，背包容量为5kg：

物品	价值 ( $v_i$ )	重量 ( $w_i$ )
1	$10	1kg
2	$12	1kg
3	$15	2kg
4	$20	3kg

最终得到的最优解的价值为42。

总结

动态规划是一种非常强大的通用工具，用于解决优化问题。与贪心算法不同，动态规划通过系统地搜索所有可能性来确保正确性，同时存储结果以避免重新计算，从而提供效率。