0%

动态规划

简介

动态规划(dynamic programming),这里的 programming 不是编程的意思,而是表格的意思,意味着将求出的子问题的解存到表格中,以便下次用到时直接查表取出。动态规划与分治法类似,都是通过组合子问题的解来求解原问题。是典型的以空间换取时间的时空权衡的例子。

原理

适合用动态规划求解的问题的两个要素:最优子结构子问题重叠

步骤

动态规划求解的一般步骤:

(1)刻画一个最优解的结构特征。

(2)递归地定义最优解的值。

(3)计算最优解的值,通常采用自底向上的方法。

(4)利用计算出的信息构造一个最优解。

应用

动态规划有着很规范的范式,一般按照步骤来。

最长公共子序列

刻画最长公共子序列的特征

我们很容易用“剪切-粘贴”技术证明:两个序列的 LCS 包含这两个序列前缀的 LCS。即 LCS 问题拥有最优子结构。

一个递归解

计算 LCS 的长度

我们使用两个表 c 和 b。

Snipaste_2020-05-05_18-20-06

构造 LCS

沿着表 b 的箭头方向,从右下角开始,打印出公共元素即可。

作业排程

钢条切割

矩阵链乘法

矩阵链乘法就是寻找一个最优括号化方案,使得需要的标量乘法计算次数最少。

最优括号化方案的结构特征

最优括号化方案拥有最优子结构,我们可以使用“剪切-粘贴”方法很容易得证明,最优括号化方案包含其子链的最优括号化方案。

一个递归求解方案

计算最优代价

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MATRIX-CHAIN-ORDER(p)
n = p.length-1
let m[1..n 1..n] and s[1..n-1,2..n] be new table
for i = 1 to n
m[i,i] = 0
for l = 2 to n
for i = 1 to n-l+1
j = i+l-1
m[i,j] = ∞
for k = i to j-1
q = m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]
if q < m[i,j]
m[i,j] = q
s[i,j] = k
return m and s

构造最优解

设计一个算法输出括号化方案。