浅谈动态规划

Hello_World

---

简单dp

1. 经典的青蛙跳台阶

一只青蛙要从一楼跳到二楼，它每一步可以跳一个台阶或者两个台阶，从一楼到二楼有 $n$ 个台阶，请问这只青蛙有多少种跳法？

提示：定义到达第 $i$ 个台阶的总方案数为 $dp(i)$，假设已知 $dp(1),dp(2),\cdots,dp(i-1)$，如何求出 $dp(i)$？
如果是第一次碰到这个问题，请多思考一会儿，再查看答案。

2. 忙碌的机器人

有一个机器人，它每天都在一个书架前整理图书，它每次可以从第 $i$ 个书架移动到第 $i+1$ 或者第 $i-1$ 个书架前，现在有 $n$ 个并列的书架，编号为 $1,2,\cdots,n$，告诉你机器人的起点 $start$ 和终点 $end$，问这个机器人从 $start$ 走 $m$ 步，走到 $end$ 总共有多少种走法？

提示：定义在第 $t$ 时刻到达第 $i$ 个书架的总方案数为 $dp(t,i)$，假设已经知道 $dp(t-1,1),dp(t-1,2),\cdots,dp(t-1,n)$，如何求出 $dp(t,i)$？
如果已经想到如何解决，就对照答案来看一下自己的 $dp$ 方程对不对，或者是否比答案更好吧？

比青蛙跳台阶更经典的dp

3.1 01 背包

有 $n$ 个石头，每个石头有自己的价值 $c_i$ 和体积 $v_i$，现在你有一个背包，这个背包只能放总体积为 $V$ 的石头，每个石头要么放进背包，要么不放进背包，要如何对石头进行取舍，才能使这个背包装入的石头价值最大，问这个最大的价值是多少？

经过上面两道简单的 $dp$ 问题，你能想出如何定义这个问题的状态吗？
如果之前没有见过这个问题的话，应该是不能的，如果之前没见过这个问题，自己推出了 $dp$ 方程的话，可以在发的 $Contests$ 上自行验证一下，因为这题非常非常经典，所以我直接给出状态的定义和 $dp$ 方程了。
定义 $dp(i,j)$ 表示，当背包体积为 $j$ 时，放到第 $i$ 个石头的时候，能够取得的最大价值。则：

$$dp(i,j)=\begin{cases}dp(i-1,j)&j<v_i\\\max(dp(i-1,j), dp(i-1,j-v_i)+c_i)&j\geq v_i\end{cases}$$
由于该 $dp$ 方程的无前效性，所以可以将二维的 $dp$ 写成一维的 $dp$，一般这个循环写为：

memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; ++i) {
    for(int j = V; j >= v[i]; --j) {
        dp[j] = max(dp[j], dp[j - v[i]] + c[i]);
    }
}

3.2 完全背包

题目背景与 $01$ 背包相同，只是由 $n$ 个石头改为 $n$ 种石头，每种石头有无穷多个，仍然问背包能够放下的最大价值。

完全背包的 $dp(i,j)$ 状态的定义为：当背包体积为 $j$ 时，放到第 $i$ 种石头的时候，能够取得的最大价值。方程为：

$$dp(i,j)=\max(dp(i-1,j-k\times v_i)+k\times c_i)\quad\quad k\in[0,\lfloor\frac{j}{v_i}\rfloor]$$
由于在得到 $dp(i,j-v_i)$ 时，已经尽量多地把第 $i$ 种石头放入了背包，所以也可以将 $dp$ 拍成一维。写法如下：

memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; ++i) {
    for(int j = v[i]; j <= V; ++j) {
        dp[j] = max(dp[j], dp[j - v[i]] + c[i]);
    }
}

3.3 多重背包

题目背景与 $01$ 背包相同，只是由 $n$ 个石头改为 $n$ 种石头，第 $i$ 种石头有 $a_i$ 个，仍然问背包能够放下的最大价值。

由于 $a_i$ 通常都比较大，将其等价地看作 $n=\sum_i^na_i$ 的 $01$ 背包显然是要炸的，$01$ 背包的时间复杂度为 $O(nV)$，若强行等价，那么这个 $n$ 就很容易超出 $10^9$。多重背包转化为 $01$ 背包可以将第 $i$ 种石头的 $a_i$ 按照二进制拆法拆成 $a_i=\sum_j^tb_j\times2^j,\quad b_j!=0$，这样就可以快速将 $a_i$ 个石头拆成 $\sum_j^tb_j$ 个石头，且这个值约等于 $\log a_i$，时间复杂度可以降到 $O(Vn\log n)$。

3.4 Pick The Sticks（背包题改）

有一个容器，这个容器可以不重叠地放置木棒，只要保证放置在上面的木棒的中点处于容器的支持面内，这个木棒就可以被放置在容器上，第 $i$ 个木棒有相应的长度 $len_i$ 与价值 $v_i$，求这个容器的最大木棒价值和。

写题解太烦，周六下午再讲吧。

4. 最长上升子序列

给定一个长度为 $n$ 的序列，求这个序列的最长递增子序列。

我第一次做这题的时候想到的是 $O(n^2)$ 的做法，如果这题让你们自己想的话，也可能想得出 $O(n\log n)$ 的做法，建议先想想吧。
定义状态 $dp(i)$ 表示到第 $i$ 个数字时，最长上升子序列的长度，这里直接给出 $O(n^2)$ 解法的 $dp$ 方程：

$$dp(i)=\max(dp(j))+1\quad num_j<num_i,1\leq j<i$$
$O(n\log n)$ 的做法相当于把 $O(n^2)$ 的做法放到 $set$ 里面优化一个 $\log n$（不是直接放到 $set$ 里）。

5. 最长公共子串

给定两个长度分别为 $n$ 和 $m$ 的字符串，问这两个字符串的最长公共子串的长度。

这题 $O(n^2)$ 的做法还是很容易想出来的，就当作前面这些问题的 $dp$ 练习题吧，如果想不出状态的定义，再看看提示，看完提示再想想能不能自己推出 $dp$ 方程。

提示：定义状态 $dp(i,j)$ 表示以第一个串以第 $i$ 个字符为结尾的连续子串，与第二个串以第 $j$ 个字符为结尾的连续子串的最长公共子串长度。

这题难度很低，只是因为这题实在是很经典，所以也拿出来做一做，现在有更快的后缀数组的$O(n\log n)$ 的做法。可能很多公司笔试题会用这个来考一考大家的 $dp$ 思想（其实一般就是直接裸考这道题，不做什么其他变换，只能考出你有没有见过这题，和有没有 $dp$ 思想没有半毛钱关系），这题值得借鉴的是 $dp(i,j)$ 这种状态的定义，在很多两个字符串的题目当中，会用到这种状态的定义。

状态压缩

就讲一道题吧，估计你们是碰不到状态压缩的题目的：Engineer Assignment

dp 优化

如果发现 $dp$ 的时间复杂度爆炸，看看这个 $dp$ 方程能否转化为矩阵相乘的形式，如果可以转化为矩阵相乘的形式，那么就可以用矩阵快速幂进行优化。