Dynamic Programing

基础问题:爬楼梯

假设你正在爬楼梯,需要爬n阶你才能到达楼顶.每次你可以爬1或2个台阶,求有多少种不同的方法爬到楼顶,我们要求算法在线性时间内解决这一问题.

我们知道爬楼梯的方法中,最后一步有两种可能:

1. 最后一步爬一个台阶;
2. 最后一步爬两个台阶.

如果我们能知道这两种情况下爬楼梯的方法数,那么总的方法数就是两种情况相加.我们发现,如果最后一步爬1个台阶,那么爬楼梯的方法数就是爬$n-1$阶楼梯的方法数;如果最后一步爬2个台阶,那么爬楼梯的方法数就是爬$n-2$阶楼梯的方法数.由此我们就可以得到一个递推关系:$f(n) = f(n-1)+f(n-2)$.

这是一个斐波那契数列,它的耗时特别长,因为它模仿了斐波那契数列,中间有非常多的冗余计算.那么自然我们想要寻求一个方法来减少冗余计算.

我们只要用一个数组把已经计算出来的值存起来:首先初始化斐波那契数列的第0和1项,然后基于此计算第2项,放在数组下标2的位置;再基于第一项和第二项计算出第三项;以此类推直接算到第n项.这种方法显然是线性的时间复杂度,但是由于使用了数组存储,增加了额外的空间开销,所以这是典型的“空间换时间”,这一思想也被我们称为“记忆化”.

换句话说,递归是一种“自上而下”的方法,符合我们的直觉,而数组存储就是一种“自下而上”,从底部构起原问题.

---

下面给出动态规划的一般范式.动态规划通常用来求解最优化问题(optimization problem).这类问题可以有很多可行解,每个解都有一个值,我们希望寻找最优值(最小或最大值)的解.我们称这样的解为问题的一个最优解(an optimal solution),而不是最优解(the optimal solution),因为可能有多个解都达到最优值.

我们通常按如下4个步骤来设计一个动态规划算法:

1. 刻画一个最优解的结构特征;
2. 递归地定义最优解的值;
3. 计算最优解的值,通常采用自下而上的方法;
4. 利用计算出的信息构造一个最优解.

但是如果我们只需要一个最优解的值,而不用最优解本身,那么我们可以忽略步骤4;但是如果需要做步骤4,那么可能需要在步骤3的过程中维护一些额外信息,用来构造最优解.

加权独立集合问题

问题描述

你是一个专业的小偷,计划偷窃沿街的房屋.每间房内都藏有一定的现金.影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警.给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况下,一夜之内能够偷窃到的最高金额.

最优子结构

把问题抽象为一个无向图G,它所有点都在一条直线上,且每个点都有一个非负权重;并且称G的独立集合是指顶点互不相邻的子集(即独立集合不会包含一条边上的两个点),那么我们的任务就是求解一个具有最大顶点权重和的独立集合.

从后往前开始考虑,首先考虑最后一个点$v_n$是否在最优解$S$中,分为以下两种情况:

1. $v_n$不在$S$中,那么我们可以把$S$看作前$n-1$个点构成的路径图$G_{n-1}$组成的子问题的一个可行解.实际上,$S$一定是最优解,因为假设我们可以找到一个更优的解$S^*$,$S^*$作为子问题的最优解,是原问题的可行解,因此一定不会优于原问题的最优解$S$,但是我们前边假设$S^*$优于$S$,这就造成了矛盾,所以$S$一定是最优解;
2. $v_n$在$S$中,那么$v_{n-1}$就不能在$S$中,那么整个问题的最优解就是$G_{n-2}$的最优解加上$v_n$.

那么我们可以写出递推关系:

$$W_n=\max\{{W_{n-1},W_{n-2}+w_n}\}\notag$$

如此就完成了动态规划框架的前两步,接下来就是写代码求解:

int a[length-(n+1)];
a[0] = 0;
a[1] = w1;
for (int i = 2;i <= n;i++)
{
  a[i] = findmax(a[i-1],a[i-2]+wi);
}

显然这个算法的时间复杂度是$O(n)$

解的重构

我们需要求出最优解本身,而不是只有一个数字.从数组a中,我们首先可以看出最后一个点是否在最优解中,由于:

$$W_n=\max\{{W_{n-1},W_{n-2}+w_n}\}\notag$$

那么如果$W_n=W_{n-1}$,那么最后一个点就不在最优解中,此时回退到$G_{n-1}$,重构$G_{n-1}$的最优解;

如果$W_n \neq W_{n-1}$,那么最后一个点在最优解中,回退到$G_{n-2}$重构最优解

背包问题

问题描述

最基础的背包问题,即0-1背包问题.描述如下:我们有$n$个物品,每个物品重量为$s_i$,价值为$v_i$,我们有一个容量为$C$的背包,希望找到一个最优的装载方案,使背包中物品的总价值最大.每个物品要么完整放进去,要么不放进去,所以称为0-1背包问题

最优子结构

1. 如果第$n$个物品不在最优解$S$中,那么可以把它看成仅有前$n-1$个物品组成的子问题的最优解;
2. 如果第$n$个物品在最优解$S$中,那么我们希望$S-\{n\}$是前$n-1$个物品组成的子问题的最优解,但是这是错误的!因为如果$S-\{n\}$是前$n-1$个物品组成的子问题的最优解的话,那么我们就不可能再把第$n$个物品放进去了,因为这时背包已经满了.因此对子问题改动:==$S-\{n\}$应该是前$n-1$个物品在背包容量为$C-\{s_n\}$情况下的最优解==

我们需要一个二维数组来存储子问题的解,设$V_{i,c}$表示总重量不超过$c$的前$i$件物品组成的子集的最大总价值,由此得到如下递推关系:

$$V_{i,c}= \left\{ \begin{matrix} V_{i-1,c} \ ,s_i >c\ ;\\ max\{V_{i-1,c},V_{i-1,c-s}+v_i\} \ ,s_i \leq c. \end{matrix} \right.\notag$$

解的重构

与上一个问题一样,看第$n$件物品是否在最优解中,从后往前找.

为代码如下:

S := 0
c := C
for i = n downto 1 do
	if si <= c and A[i-1][c-si]+vi >= A[i-1][c] then
	S := S + i
	c := c - si
return S

矩阵乘法的计算顺序

计算一系列矩阵链相乘的顺序,使得总的计算代价最小.

最优子结构

首先考虑矩阵链相乘$M_1,M_2,\dots M_n$,每个矩阵的大小为$r_{i-1}\times r_i$,记

$$M_{ij} = M_iM_{i+1}\dots M_j\notag$$

我们首先想到仿照前两个问题的思路,根据最后一个矩阵可能的相乘方式划分最优解的可能性.例如,我们可以有以下的计算方式:$M_{1,n-1}M_n$和$M_{1,n-2},M_{n-1,n}$,但是这显然不能包含所有的情况.

所以转而回到动态规划最开始的想法,我们想知道第一刀应该切在哪里,而不是最后一个物体在不在最优解中.

我们考虑所有的

$$M_{1,i}M_{i+1,n}, \ 1 \leq i \leq n-1 \notag$$

分解,那么总的最小时间应当等于$M_{1,i}$和$M_{i+1,n}$的最小时间求和加上$M_{1,i}$和$M_{i+1,n}$相乘所需的时间(即$r_0r_ir_n$),我们可以得到$n-1$种情况的最优时间,接下来只要找到他们中的最优值就是整个问题的最优解.递推式如下:

$$m_{ij}=\left\{ \begin{matrix} 0, \ i=j;\\ \min_{i\leq k<j}{m_{ik}+m_{k+1,j}+r_{i-1}r_kr_j}, \ i<j \end{matrix} \right.\notag$$

我们应当按照矩阵链的长度从小到大的顺序计算最优解.即最外层循环应当是按$M_{ij}$中$i-j$的大小递增的顺序,这样base case是矩阵链长度为1($j=i$)的全0,然后是长度为2($j-i=1$)的情况,然后逐步迭代到最后长度为$n$到情况.时间复杂度是$O(n^3)$.

下面是PPT上的伪代码:

void OptMatrix( const long r[ ], int N, TwoDimArray M ) 
{   
  int  i, j, k, L; 
  long  ThisM; 
  for( i = 1; i <= N; i++ )   M[i][i] = 0; 
  for( k = 1; k < N; k++ ){ /* k = j - i */ 
  	for( i = 1; i <= N - k; i++ ) { /* For each position */ 
			j = i + k;    
      M[i][j] = Infinity; 
			for( L = i; L < j; L++ ) { 
	    	ThisM = M[i][L] + M[L + 1][j] + r[i - 1] * r[L] * r[j]; 
	    	if ( ThisM < M[i][j] )  /* Update min */ 
					M[i][j] = ThisM; 
			}  /* end for-L */
     }  /* end for-Left */
  }
}

解的重构

用一个二维数组记住每一个子问题

$$m_{ij}=\min_{i\leq k<j}{m_{ik}+m_{k+1,j}+r_{i-1}r_kr_j}\notag$$

对应的最优的分点$k$,然后算出总问题的最优解及最优分点后,再找左右两半子问题的最优分点,依次类推,用中序遍历的思想将分点输出,只用线性时间.

最优二叉搜索树

给定一串按字母序排好的单词和他们出现的频率.要求构建一棵二叉搜索树使得总的期望存取时间最小.在一棵二叉搜索树中,访问深度$d$处的一个元素所需要的比较次数是$d+1$,因此如果$w_i$被放在深度$d_i$上,那么我们就要将$\sum_{i=1}^{N}{p_i(1+d_i)}$极小化.

我们需要知道最优根节点在哪里,然后才能进行划分.如果我们知道最优根节点为$w_k$,那么左子树一定是$w_1,w_2,\dots w_{k-1}$对应的最优二叉搜索树,右子树则是$w_{k+1},w_{k+2},\dots,w_n$对应的最优二叉搜索树.那么我们就有了递推式:

$$c_{ij}=\sum_{k=i}^{j}{p_k}+min_{i\leq k <j}\{c_{i,k-1}+c_{k+1,j}\}\notag$$

我们加上第一项$\sum_{k=i}^{j}{p_k}$的意义在于,由于根节点的存在,所有$i$到$j$到单词都加深了一层.

最短路

对于图上的所有点,找出每一对点之间的最短距离.我们可以定义$D^k[s][v]$为从$s$到$v$的最多经过$k$条边的最短路径长度,整个图为$G=(V,E)$,如果$a$到$b$有一条边,那么这条边的长度记为$l_{ab}$,我们有如下递推式:

$$D^k[s][v] = min \left\{ \begin{matrix} D^{k-1}[s][v], \ case 1;\\ \min_{(w,v)\in E}{\{D^{k-1}[s][w]+l_{wv}}\}, \ case2. \end{matrix} \right.$$

• case1:最短路径$P$只有$k-1$条或更少的边,那么直接继承子问题的解即可;
• case2:$P$有$k$条边,设$P^{'}$为$P$中前$k-1$条边,并且$(w,v)$是其最后一次的跳跃,那么$P^{'}$也是$s$到$w$的$k-1$条边的最短路径.

我们希望通过这种方法,还能够监测负环,我们有如下的定理.

定理 输入图$G$不包含负环当且仅当$D^n[s][v]=D^{n+1}[s][v]$对所有的目标顶点$v$都成立.其中$n$是图的顶点数