动态规划入门

Those who cannot remember the past are condemned to repeat it. ——Dynamic Programming

CSDN链接

动规具备的特点

• 把原来的问题分解成几个相似的子问题。
• 所有的子问题都只需要解决一次。
• 储存子问题的解。

一个例子：斐波那契数列(Fibonacci)

$0,1,1,2,3,5,8,13,…$

如果设该数列的第 $n$ 项为 $F(n)$ ，那么
$$ \enclose{downdiagonalstrike}{F(n) = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n \right]} $$
$$ F(n) =
\begin{cases}
F(n-1)+F(n-2)&&\text{n $\geq$ 2} \\
1&&\text{n = 1} \\
0&&\text{n = 0} \\
\end{cases}
$$

这里我们把求 $F(n)$ 分解成了求 $F(n-1)$ 和 $F(n-2)$ 两个子问题。

假设现在需要计算 $F(6)$ 的值，那么我们就需要计算 $F(5)$ 和 $F(4)$ ，对于 $F(5)$ 我们需要计算 $F(4)$ 和 $F(3)$ ，对于 $F(4)$ 我们需要计算 $F(3)$ 和 $F(2)$ ，对于 $F(3)$ 我们需要计算 $F(2)$ 和 $F(1)$ ，对于 $F(2)$ 我们需要计算 $F(1)$ 和 $F(0)$ 。如下图

方法一：递归

我们先用递归来实现

int F(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    return F(n-1) + F(n-2);
}

当 $n\geq30$ 时，速度就很慢了。不难发现此过程中有大量的重复计算，且不符合「所有的子问题都只需要解决一次」的特点。

解决这个问题，就要用到动态规划的第三个特点——「储存子问题的解」。

我们将已经计算过的结果储存起来，在下次需要计算的时候直接调用即可。如下图

方法二：自顶向下的备忘录法

#define N 90
long long fib[N];
long long F(int n) {
    if(fib[n]) return fib[n];
    if(n == 0) fib[n] = 0;
    else if(n == 1) fib[n] = 1;
    else fib[n] = F(n-1) + F(n-2);
    return fib[n];
}

这里我们用了 fib 数组来储存已经计算过的结果。

这个方法还是用到了递归，不管怎样，计算 $F(6)$ 时最后还是要计算出 $F(1)$ 、 $F(2)$ 、 $F(3)$ $\cdots$
那为何不先计算出 $F(1)$ 、 $F(2)$ 、 $F(3)$ 呢？

也就是先计算子问题，再由子问题计算父问题。

方法三：自底向上的动态规划

#define N 90
long long F(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    long long fib[N]={0,1};
    for(int i=2; i<=n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib[n];
}

上面这段代码也是利用数组保存了先计算的结果，为后面的调用服务。

观察参与循环的只有 $i$ 、 $i-1$ 、 $i-2$ 三项，因此该方法的空间可以进一步的压缩如下

long long F(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    long long fib_1,fib_2,fib_3;
    fib_1 = fib_2 = 1;
    for(int i=2; i<=n; i++) {
        fib_3 = fib_2 + fib_1;
        fib_1 = fib_2;
        fib_2 = fib_3;
    }
    return fib_3;
}

两个性质

• 可推导性
  每个状态均可以由之前的状态演变形成
• 无后效性
  当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。

Future never has to do with past time, but present does.

三个概念

• 最优子结构
  问题的最优解所包含的子问题的解也是最优的
• 边界
• 状态转移方程

例如，在「求斐波那契数列问题」中

「边界」是 $F(0)$ 和 $F(1)$
「状态转移方程」是 $F(n)=F(n-1)+F(n-2)$

另一个例子：最长上升子序列（LIS）

给一个长度为 $n$ 的序列 $a$ ，问最长的子序列（ $a[i_1],a[i_2],\cdots,a[i_k]$ ）的长度 $k$ ，满足 $i_1<i_2<\cdots<i_k$ 并且 $a[i_1]<a[i_2]<\cdots<a[i_k]$ 。

方法一

用 $f[i]$ 表示 $a[1]$ 到 $a[i]$ 中，以 $a[i]$ 结尾的LIS的长度。

状态转移方程：
$$ f[i] = \max \limits_{1\leq j<i,a[j]<a[i]} {f[j]} +1 $$

方法二

用 $f[i][k]$ 表示 $a[1]$ 到 $a[i]$ 中，长度为 $k$ 的LIS的末尾元素的最小值

状态转移方程：
$$ f[i][k] =
\begin{cases}
\min (a[i],f[i-1][k])&& {a[i]>f[i-1][k-1]} \\
f[i-1][k]&&{a[i]\leq f[i-1][k-1]} \\
\end{cases}
$$

方法二·改

时间复杂度为 $O(n\ log\ n)$ 的算法
$\scriptsize{略}$

总结

接下来，我们就进行一下总结

递归到动规的一般转化方法

递归函数有 $n$ 个参数，就定义一个 $n$ 维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始， 逐步填充数组，相当于计算递归函数值的逆过程。

动规解题的一般思路

1. 将原问题分解为子问题
   把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决。
   子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。
2. 确定状态
   在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。
   所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。
   整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。
3. 确定一些初始状态（边界状态）的值
4. 确定状态转移方程
   定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移——即如何从一个或多个“值”已知的 “状态”，求出另一个“状态”的“值”（递推型）。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。

动规与其他算法的区别

贪心

贪心的每一步都做出在当时看起来最优的决策或选择，做完一次决策后，再用同样的策略去解决接下来的子问题。
贪心算法无法保证求得全局最优解。

分治

分治法是将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。
而动态规划是应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。

动规相关问题

• 子序列问题
  • 最长上升子序列（LIS）
  • 最长公共子序列（LCS）
  • 最长回文子序列（LPS）
• 记忆化搜索
• 背包问题
  • 01背包
  • 完全背包
  • 多重背包
  • 混合背包
  • 二维费用背包
  • 分组背包
  • 有依赖的背包
  • 泛化物品的背包
• $\cdots\cdots$

简单例题

以下例题来自洛谷 【动态规划1】动态规划的引入 题单

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
P1434 [SHOI2002]滑雪
P2196 挖地雷
P4017 最大食物链计数
P1048 采药
P1616 疯狂的采药
P1802 5倍经验日
P1002 过河卒

Views: 83