【动态规划】（一）理解动态规划

很早以前就接触了动态规划，然而那时候的我对动归的理解就是背转移方程，结果题目稍微变一下形就不会辣。

于是我打算写这篇博客，来总结自己对动态规划的认识，以及自己少得可怜的做题经验。

写在前面

我们求解离散最优化问题的过程，本质上就是遍历状态空间的过程。

状态与状态空间

定义多元组 \(s_k = (a_{k,1}, a_{k,2}, a_{k,3}, ..., a_{k,n})\) 表示状态，定义集合 \(S = \{s_1, s_2, s_3, ..., s_m\}\) 表示状态空间。

我们称 \(|S|\) 为状态 \(s_k\) 的 规模 ，状态的规模直接决定了遍历状态空间的时间复杂度。

从 状态空间搜索 到 动态规划

状态空间搜索和动态规划的本质都是遍历状态空间，为什么状态空间搜索往往是指数级时间复杂度的，而动态规划却往往是多项式时间复杂度的呢？

在上文中我们提到：状态的规模直接决定了遍历状态空间的时间复杂度 ，那么我们猜想：状态空间搜索与动态规划的区别在于两者的状态规模不同 。

Example 1 : 01背包问题

这个问题有两种解法：

1. 枚举每个物品选或不选，计算最大价值和。
2. 定义 \(F(i, j)\) 表示前 \(i\) 个物品中，物品重量和为 \(j\) 时的最大价值和。则有 \(F(i, j) = \max\{F(i - 1, j),\ F(i - 1, j - w_i) + v_i\}\) ，\(\mathop{\max}\limits_{1 ≤ p ≤ W} F(n, p)\) 即为所求。

第一个算法——状态空间搜索是 \(O(2^n)\) 的，第二个算法——动态规划是 \(O(nW)\) 的，为什么会有这样的区别呢？

我们来看看两个算法分别定义的状态：

1. 算法一：定义 \(s_k = P\) ，\(P\) 为已选的物品集合，那么状态空间 \(S = \{X | X \subseteq U\}\) ，\(U = [1, n] \cap N\) 。显然有 \(|S| = 2^n\) 。
2. 算法二：定义 \(s_k = (i, j)\) ，那么状态空间 \(S = \{(i, j) | i \in U_1,\ j \in U_2\} = U_1 \times U_2\) ，\(U_1 = [1, n] \cap N\) ，\(U_2 = [1, W] \cap N\) 。显然有 \(|S| = nW\) 。

现在我们可知：状态空间搜索（各种深广搜）与动态规划的本质区别在于 状态不同和状态规模不同 。

实际上，状态空间搜索也是一种动态规划，我们可以写出上文中算法一的状态转移方程：\(F(X) = \left\{ \begin{matrix} 0, &\mathop{\sum}\limits_{x \in X}{w_x} \gt W \\ \mathop{\max}\limits_{x \in X}\{ F(X\ \backslash\ \{x\}) + v_x \}, &\mathop{\sum}\limits_{x \in X}{w_x} \leq W \\ \end{matrix} \right.\)

看着是不是很像状态压缩动态规划？其实它就是状压。

状态设计 与 状态转移方程设计 的一般思路

开坑待填。