DP动态规划问题

动态规划方法常常应用于解决优化问题,通常分析一个问题是否可以用动态规划方法求解可以从以几个方面判断:

  1. 原问题可分,原问题的数据结构(array,tree,graph)可以进行划分。
  2. 原问题有最优子结构。
  3. 原问题的最优解将由一系列的子问题的解组合而成。

动态规划法的一般思路为,通过枚举所有可能的分类策略,来组合成最优解。关键步骤在于找到一个合适的递推公式,将原问题转化为一个多步决策的问题。

下面是重点介绍几个DP问题,以及他们的解题过程。

矩阵连乘问题:
问题描述:给定n个矩阵 $(A_1,A_2,A_3…..A_n)$,其中$A_i$与$A_{i+1}$是可乘的,i=1,2,…n-1。考察n个矩阵的连乘积 $A_1A_2A_3,….A_n$ 。由于矩阵乘法满足结合律,试提出矩阵连乘积最优计算次序,使得计算量最小。
分析:确定矩阵相乘次序的问题等价于在原始序列上添加括号。通过改变不同位置上的矩阵的计算次序,能够减小矩阵乘法所需要的计算次数。经典的序列划分问题。现在来判断该问题是否可以用动态规划方法来求解:

  1. 原问题是否可分:假设找到一个位置k添加括号能够得到最优解,因此将原问题转化为(1,k)与(k+1,n)两个序列,子问题性质与原问题完全相同,因此问题可分。
  2. 问题的递推公式(最优子结构): $$ OPT[1,n] = OPT[1,k]+OPT[k+1,n] + p_0p_kp_{n+1} $$
  3. 由于子问题之间不存在相互关系,原问题的最优解由一系列子问题的最优解组成。

矩阵连乘问题求解:
若使用递归的方法,对原问题进行枚举,枚举每一种加括号的方式,能够得到原问题的解,但是计算量巨大,对这道题来说,他的时间复杂度是:$2^{n-1}$算法框架如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
recursive_matrix_chain(i,j)
{
if i == j then
return 0
OPT(i,j) = INF
for k=i to j-1:
q = recursive_matrix_chain(i,k)+
recursive_matrix_chain(k+1,j)+
p[i]*p[k+1]*p[j+1]
if q<OPT(i,j):
OPT(i,j) = q
return OPT(i,j)
}

memorizing technique:动态规划法的英文为dynamic programming,programming 这个词最早有tabular这个词演化而来,tabular意为表格,因此DP方法可以直观的理解为动态填表法。动态规划法的一个重要思想就是:对子问题的结果进行保存。
算法框架如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
memorize_matrix_chain(i,j)
{
if OPT[i,j] != NULL: //如果子问题已经算过了,就可以不用算了
return OPT[i,j]
if i == j: //递归法的出口
OPT[i,j] = 0
else:
for k = i to j - 1: //对每一个子问题划分情况进行枚举
q = memorize_matrix_chain(i,k)+
memorize_matrix_chain(k+1,j)
+ p[i]*p[k+1]*p[j+1]
if q < OPT[i,j]:
OPT[i,j] = q
return OPT[i,j]
}

该方法的时间复杂度为: $T(n) = O(n^3)$ ,动态规划问题的时间复杂度计算方法为:子问题的个数子问题的时间,对于本题: $O(n^2)n = O(n^3) $
一种更快的实现方法,从底往上计算省略递归步骤。 具体思路是:先将分割的长度由2到n进行遍历,每次拿出一个长度然后对其进行由i到j每个位置的划分,均求一个最大,对每次的结果进行保存,最后得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
matrix_chain_multiplication()
{
for i = 1 to n :
OPT[i,i] = 0
for l = 2 to n : //子串的长度由2到n递增
for i = 1 to n - l + 1: //l长度下,对i所有可能位置进行遍历
j = i + l -1 // j移到子串的最后位置上
opt[i,j] = INF
for k = i to j - 1: //对每一个位置均遍历一下括号的位置
q = opt[i,k]+opt[k+1,j]+p[i]*p[k+1]*p[j+1]
if q < opt[i,j]:
opt[i,j] = q
s[i,j] = k
return opt[1,n]
}

0/1背包问题
给定一个集合其中有S个物品,每个物品i有一个重量 w_i 和一个价值 v_i ,每个物品只有一个,你有一个能装重量为W的背包。问怎么装使得所装物品的价值最大。

分析:我们将0/1背包问题转化成一个多步决策的问题,在第i步决定是否选择第i个物品。因此有一下的递推表达式:
$$ opt({1,2,…n},W) = \max \begin{cases} opt({1,2,…n-1},W) & opt({1,2,…n-1},W-w_n)+v_n \end{cases}
$$
算法框架如下:

1
2
3
4
5
6
7
8
9
Knapsack(n,w)
{
for w = 1 to W:
OPT[0,w] = 0
for i = 1 to n: //现在拿i个物品
for w = 1 to W: // 现在拿出w个空间来装
if w > w[i]: //当前拿出的空间够装现在的货物
OPT[i,w] = max(opt[i-1][w],opt[i-1][w-w[i]]+v[i])
}

回退法判断物品是否被取走:

1
2
3
4
5
6
7
8
9
10
void traceback()
{
for i = n to 2:
if(m[i][c] == m[i-1][c]):
x[i] = 0
else:
x[i] = 1
c -= w[i]
x[1] = m[1][c]>0? 1:0;
}

时间复杂度为 O(nW) 伪多项式时间。$ O(nW) = O(n*2^{logW})$ ,W为输入的长度,当W很大时,算法效率很低。需要注意的是,我们选择物品的顺序是从头到尾挑选,而不是在一个子集中随机挑选。

最小覆盖点问题:
问题描述:在一个图中找到最少的点,使其能够覆盖图中所有的边。

问题分析:这个问题可以用一个树的结构的分析。当选取当前的点作为最优结果中的一点时,从从改点的所有子节点作为新的子问题,否则选取所有的儿子节点,从其孙子节点作为子问题。 该问题的最优子结构为:
$$ opt(root) = \min ( 1 + \sum_copt(c) , children + \sum_gopt(g) )$$
算法框架如下:

1
2
3
4
5
6
7
vertex_cover(root)
{
if(root == NULL):
return 0
opt(root) = min(sum_of_child+opt(g),1+opt(c))
return opt(root)
}

动态规划问题的适用于求解那些子问题存在大量重复的问题,可以通过存储中间结果的方式大大缩小程序的复杂度。通常的求解方式有递归法,动态填表法。