把一个大问题分解成很多小问题，然后把小问题的答案保存起来，避免重复计算，最后根据小问题的答案推出大问题的答案，这样的算法叫动态规划（DP）．

作用与核心思想#

• 作用：高效地解决一些复杂的问题，例如最短路径，背包问题等．
• 核心思想：把一个大问题分解成很多小问题，然后把小问题的答案保存起来，避免重复计算，最后根据小问题的答案推出大问题的答案．

概念#

• 状态：描述问题的某个子问题的情况
• 初始状态：最简单的情况，边界条件
• 状态转移方程：状态之间转换的规律，即如果得知前面的状态，怎么退出后面的状态（一种状态一般会由多种状态堆叠而成）
• 最终状态：最终的答案

例题：求斐波那契数列的第 n 项

设定一个数组为 dp[i]，表示斐波那契数列的第 i 项

状态：dp[i] 表示前两个数之和

初始状态：dp[1]=1，dp[2]=1

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

最终状态：dp[n]

---

动态规划基本步骤#

1. 定义状态
2. 确定初始状态
3. 找出状态转换方程（可以倒过来思考，先想好每一个状态可以迁移到哪些状态）
4. 返回最终状态

性质#

• 最优子结构：一个问题的最优解可以由它的子问题来得出
• 无后效性：如果知道了一个状态的值，那么就不需要再考虑它是怎么得到的，也不需要考虑它之前的状态是什么．因为状态的值只取决于当前问题的情况，并不受之前具体选择的影响，简化状态转移方程，并且避免一些不必要的计算

常见优化方案#

• 预处理
• 影响参数化，参数结果化
  • 如果一个问题有后效性，考虑将影响参数化，增加一维参数
  • 尽力将参数消去，这样可以减少时间复杂度

典型案例#

最长上升子序列问题#

给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列．请输出这个序列的最长上升子序列的长度．最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的．

带入基本步骤：

设立原数组为 a 数组，长度为 n

状态：dp[i] 表示 a[1]~a[i] 中最长子序列的长度

初始状态：dp[1] = 1

状态转移方程：$dp[i]=max(dp[j]+1),j<i \land a[j]<a[i]$，即枚举在 a[i] 之前且小于 a[i] 的元素 a[j]，并更新 dp[i]

最终状态：max(dp[i])

时间复杂度：由于上述方案，对于每一个元素，都要枚举其前面的元素，时间复杂度为 $O(n^2)$

优化#

定义 d 数组记录所有长度为 i 的最长子序列中最后一个元素的最小值，若没有长度为 i 的最长子序列则记为 $\infty$

可知：d 数组是单调不递减的．由此，对于每一个新的节点，都有

$$dp[i] = \arg\max_{j < i,\ a[i] > d[j]} d[j]$$

其中：

• $\max f(x)$ 表示函数 $f(x)$ 的最大值（一个具体的数值）
• $\arg\max f(x)$ 表示使得 $f(x)$ 达到最大值时的 $x$ 值（自变量）

再更新 $d[j]$，$d[j]=a[i]$

时间复杂度：如果这样，那么可以二分查找符合目标的 j ，时间复杂度 $O(logn)$

01 背包#

有 $n$ 个物品和一个容量为 $w$ 的背包，每个物品有重量 $w_i$ 和价值 $v_i$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量．

在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的 0 和 1，这类问题便被称为0-1 背包问题．

定义 dp[i][j] 表示考虑前 i 个元素，背包占用空间达到 j，所能够获取的最大空间．初始时 dp[1][0]=0

对于所有的物品，都有选和不选两种选择，因此，有如下的状态转移方程：

$$dp[i][j] = max(dp[i-1][j-w[i]] + a[i], dp[i-1][j])$$

不难发现，dp[i][j] 依赖于以下项：

• dp[i-1][j]
• dp[i-1][j-w[i]]

由于第一维只与 i-1 有关，因此，可以倒着遍历 j，如果这样，第一维状态就可以省去．