Unit2_1：动态规划DP

一、介绍

动态规划类似于分治法,它们都将一个问题划分为更小的子问题
最优子结构:问题的最优解包含子问题的最优解。DP适用的原因就在这
当子问题重叠时，即它们共享公共子问题时，可减小时间复杂度
DP通常用于优化问题,有许多解决方案的问题，我们想找到最好的一个
DP问题的求解思路一般就是
   先描述最优解的结构
   递归地定义最优解的值
   计算最优解的值(通常是自下而上)
   根据计算出的信息构造最优解(如果需要)

二、0-1背包问题

问题描述

$$\begin{gathered} n个商品,v_i表示第i个物品的价值,w_i表示第i个物品的重量 \\ 一个能装入W重的背包,使用背包装下价值最多的物品 \\ 限制条件:我们不能取物品的一部分，我们取整个物品，或者什么都不取。 \\ (这就是为什么它被称为0-1背包。) \end{gathered}$$

分析

设$V[i,w]表示重量为w背包,在前i种商品选择的最大价值$
对于第i个物品,我们要么选取它,要么不选择,因此最大价值转移方程为

$V[i,w]=max(V[i-1,w],v_i+V[i-1,w-w_i])$

若使用递归重复计算很多值,时间复杂度为$T(n)=O(2^W)$,因此要重复利用最优子结构的性质.

初始化:$V[0,w]=0$ $for$ $0\le w\le W$ 此时没有商品,自然没有价值
接下来按顺序填表:

伪代码

Knapsack(v,w,n,W)
for w=0 to W do
	V[0,w]=0;
end
for i=1 to n do
	for w=0 to W
		if w[i]<W then
			V[i,w] = max{V[i-1,w],v[i]+V[i-1,w-w[i]]}
		else
			V[i,w] = V[i-1,w]
		end
	end
end
return V[n,W]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

若是想要记录最优解的路径,需要维护一个$keep[i][w]$,如果选择i作为$V[i,w]$,则$keep[i][w]=1$
路径只需要
$ifkeep[n,w]=1.则选择n且继续从kepp[n-1][w-w_n]开始$
$ifkeep[n,w]=0.则不选择n且继续从kepp[n-1][w]开始$
因此路径输出代码:

K ← W
for i ← n to 1 do
	if keep[i][K] is equal to 1 then
		Output i
		K ← K-w[i]
	end
end
1
2
3
4
5
6
7

时间复杂度

两层循环,时间复杂度$T(n)=O(nW)$
本质上,DP问题是用空间换时间,将结果放在空间中而不用下次花费时间再去计算

三、钢条切割问题

问题描述

$$\begin{gathered} 给定一个长度为n的棒材和一个价格表，其中pi为长度为i的棒材的价格 \\ 确定最大的收入r_n,以及切割钢条的方案 \end{gathered}$$

分析

此题暴力解法,即遍历长度.每个点有两种选择,切$or$不切,判断哪种选择最合适即可,时间复杂度$T(n)=O(2^n)$.
考虑到最优子结构,可利用较短的杆最优收益来确定较长的,此题的状态转移如下:
$r_n=max(p_n,r_1+r_{n-1},r_2+r_{n-2},.....,r_{n-1}+r_1)$
简化定义:
$r_n=max(p_i+r_{n-i})$     $1\le i\le n$

伪代码

r[0] ← 0
for j ← 0 to n do
	q  ← -∞
	for i  ← 1 to j do
		q  ← max(q,p[i]+r[j-i])
	end
	r[j]  ← q if j != 0
end
return r[n]
1
2
3
4
5
6
7
8
9

这种做法时间复杂度$T(n)=O(n^2)$
若是需要保存切割的方案,则需要维护一个$s[n]$数组.$s[n]保存前一次切割的长度$:

r[0] ← 0
for j ← 0 to n do
	q  ← -∞
	for i  ← 1 to j do
		if q < p[i]+r[j-i] then
			q ← p[i]+r[j-i]
			s[j] ← i
		end
	end
	r[j]  ← q if j != 0
end
while n>0 do
	Output s[n]
	n ← n-s[n]
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

过程

四、矩阵链乘法

背景

$p\times q矩阵a和q\times r矩阵B的乘积C=AB是p\times r矩阵$

$c[i][j]={\sum }_{k=1}^{q}a[i][k]b[k][j]$ $for$ $1\le i\le p$ $and$ $1\le j\le r$
时间复杂度:注意$C$有$pr$个条目，每个条目需要$O(q)$时间来计算，所以整个过程需要$O(pqr)$时间

性质

矩阵乘法有结合律,$A_1{A}_2{A}_3=(A_1{A}_2)A_3=A_1(A_2{A}_3)$
因此当计算$ABC$时,有两种选择,$(AB)C=A(BC)$
$mult[(AB)C]=pqr+prs$
$mult[A(BC)]=qrs+pqs$
每种选择的时间复杂度不一样
因此矩阵链乘法需要解决的就是怎么样结合能使得计算的量最小

分析

$令A_{i..j}=A_i{A}_{i+1}...Aj$，显然，$A_{i..j}$是$P_{i-1}\times P_j$的矩阵
$A_{i..j}$可以表示为$A_{i..j}=(A_i...A_k)(A_{k+1}...Aj)=A_{i..k}{A}_{k+\mathrm{1..}j}$

当$1\le i\le j\le n$时，令$m[i,j]$表示计算$A_{i..j}$所需的最小乘法次数。最优成本可以用下面的递归定义来描述

m ( i , j ) = { 0 i f   i = j m i n i ≤ k ≤ j ( m ( i , k ) + m ( k + 1 , j ) + p i − 1 p k p j ) i f   n = 1 m(i,j)=\left\{

$$\begin{array}{ll} 0 & if \space i=j \\ min_{i \leq k \leq j} (m(i,k)+m(k+1,j)+p_{i-1}p_kp_j)& if \space n=1 \nonumber \end{array}$$ \right. m(i,j)={0mini≤k≤j​(m(i,k)+m(k+1,j)+pi−1​pk​pj​)​if i=jif n=1​

注意计算并保存$m[i,j]$的顺序是，当计算$m[i,j]$时，$m[i,k]$和$m[k+1,j]$的值已经可用，因此按矩阵链长度的递增顺序计算它们:

$m[1,2],m[2,3],m[3,4],\dots ,m[n-3,n-2],m[n-2,n-1],m[n-1,n]$
$m[1,3],m[2,4],m[3,5],\dots ,m[n-3,n-1],m[n-2,n]$
$m[1,4],m[2,5],m[3,6],\dots ,m[n-3,n]$
$\dots$
$m[1,n-1],m[2,n]$
$m[1,n]$

若需要记录分隔括号路径，需要维护一个二维数组$s[\mathrm{1..}n,\mathrm{1..}n]$，里面存储$A_{i..j}$的最优分隔k
$s[1,n]$          $(A_1..A_{s[1,n]})(A_{s[1,n]+1}...An)$
$s[1,s[1.n]]$          $(A_1..A_{s[1,s[1.n]]})(A_{s[1,s[1.n]]+1}...An)$

案例

伪代码

MatrixChain(p,n)
for i ← 1 to n do
	m[i,i] ← 0;
end
for l ← 2 to n do
	for i ← 1 to n-l+1 do
		j ← i+l-1;
		m[i,j] ← ∞
		for k ← i to j-1 do
			q ← m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]
			if q<m[i,j] then
				m[i,j] ← q
				s[i,j] ← k
			end
		end
	end
end
return m[1,n] and s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三层循环，时间复杂度$T(n)=O(n^3)$