有关「动态规划思想」的一些习题及思考

Feb. 27th, 2016


算法 动态规划 习题

最近刚开始看了看「动态规划」的一些内容,做了一些简单的习题,基本套公式就可以了,不用怎么思考,把题目和思路记录下来。

HDOJ-2084
题目:数塔问题,从顶层走到底层,每次只能走到左下或右下的数,求走到最底层时使经过节点的数字之和最大
思路:最优子结构的状态转移方程为

$$s[i][j]=max(s[i-1][j-1],s[i-1][j])+v[i][j]$$

这里$v[i][j]$表示第$i$层第$j$个数,$s[i][j]$表示到达该数时经过的数字的最大和,这里还要注意一下范围和边界条件
重叠子问题即$s[i][j]$只依赖于前一层的两个和,而这两个和按照自底向上的方法是已经求解过的,假设有$n$层,第$i$层有$i$个数,时间复杂度为$O(n^2)$
View Code in Github Repository

POJ-1050
题目:给出一个二维数组,其中包含正/负整数,求它的所有子矩形构成的数组中数字和的最大值
思路:一维最大子段和的加强版,通过降维的思想来做,首先用$v[i][j]$接收二维数组第$i$行第$j$列的数,用$s[i][j]$表示第$j$列前$i$行的和,之后求每一列的最大子段和,最后取这些和中的最大值即可。这里用公式$v[a][j]+...+v[b][j]=s[b][j]-s[a-1][j]$可以提高效率。
而一维最大子段和的最优子结构是

$$s[i]=max(s[i-1]+a[i],a[i])$$

其中假设共有n个数,$s[i]$为前$i$个数的和,$a[i]$为第$i$个数 重叠子问题在于和$s$共有$n$个,每次求解都依赖于前一个的和,时间复杂度为$O(n)$,对于这道题来说,要求$n$个最大子段和,复杂度为$O(n^2)$
View Code in Github Repository

POJ-1088
题目:给出一个二维数组,每个数字代表一个点的高度,从某一个点开始,只能向周围四个点中比该点高度小的点移动,求最长的一条路径的长度
思路:这道题的状态转移方程很好写:

$$l[i][j]=1+\max\begin{cases} l[i][j+1] & \text{if }\ l[i][j+1] < l[i][j] \\ l[i][j-1] & \text{if }\ l[i][j-1] < l[i][j] \\ l[i-1][j] & \text{if }\ l[i-1][j] < l[i][j] \\ l[i+1][j] & \text{if }\ l[i+1][j] < l[i][j] \end{cases}$$

其中$l[i][j]$表示该处的点向周围所有点移动可达的最长路径,但是在求子条件的时候,如果使用自底向上的方法进行求解,由于给定数组中的数字是无序的,所以还要进行排序,从高度最低的点依次向高度最高的点进行遍历求解。这里使用了“记备忘”的方法,采用递归的方式,可以实现自动地从小到大求解(因为每一个$l[i][j]$的值都依赖高度比它小的点的值),渐进时间复杂度没有变化,假设数组行数为$n$,列数为$m$,那么时间复杂度为$O(mn)$
View Code in Github Repository

HDOJ-1087

题目:起点和终点之间有一系列的点,每个点都有相应的数值和顺序,现在想从起点跳到终点,在经过中间点时,除了只能从前一个点跳向后一个点之外,还只能跳跃到比当前点的数值更大的点,求到达终点时所能得到的最大数值和

思路:可以看作是最长上升子序列的变体,只是目标并非最长,而是数值和最大。
最优子结构的状态转移方程为

$$l[i]=\begin{cases} max_{1\le k\le i-1}(l[k]+v[k]) & \text{if $v[k]<v[i]$} \end{cases}$$

其中$l[i]$表示到第$i$个位置所能得到的最大数值和,$v[i]$表示第$i$个点的数值
重叠子问题在于求$l[i]$时,所有的$l[k],1\le k<i$都已经求解过了,直接查表即可。假设中间点数目为$n$,如果直接递归求解,复杂度为$O(2^n)$,此处为$O(n^2)$

View Code in Github Repository

POJ-1157
题目:有$v$个花盆,$f$盆花,分别有序号$1-v,1-f$.序号靠前的花所在的花盆的序号必须要在序号靠后的花所在花盆的序号的前面。而且对于每一个花与花盆的组合都有一个美观值,求最大的总体美观值
思路:每一种花的摆放位置都有$v-f+1$种,某种花第一个可以摆放的花盆的位置与花的序号相同,状态转移方程为:

$$s[i][j]=max(s[i-1][k])+a[i][j] \quad i-1\le k<j$$

其中$a[i][j]$为第$i$种花放在第$j$个花盆里的美观值,$s[i][j]$为当第$i$种花放在$j$号花盆中时,前$i$种花的美观度最大值 最优子结构在于每一个当前的美观度最大值总是取决于之前摆放的美观度最大值,时间复杂度为$O(f\centerdot (v-f+1)^2)$
View Code in Github Repository

POJ-1191
题目:给出一个$8\times 8$的棋盘,每个格内有一个数字,现在对棋盘进行分割,要保证每次分割后剩下的部分也是矩形,并只能从剩下的部分继续分割,分割$n-1$次后棋盘有$n$个矩形。规定一个矩形棋盘的总数值为包含的小格的总数值之和,求各矩形棋盘总数值的均方差的最小值
其中均方差为$\sigma =\sqrt{\frac{\sum_{i=1}^{n}(x_i-\overline x)^2}{n}}$,平均值为$\overline x=\frac{\sum_{i=1}^{n}x_i}{n}$,其中$x_i$为第$i$个矩形棋盘的总数值
思路:首先化简均方差的公式,得到$\sigma=\frac{1}{n}\sum_{i=1}^{n}x_i^2-\overline x^2$,而且对于给定的$n$,$x_i$的值固定,所以问题化为求所有矩形棋盘数值的平方和的最小值。
由于每次分割都可以进行左右分割和上下分割,我们用坐标$(x,y)$表示一个点,用坐标组$(x_1,y_1),(x_2,y_2)$表示一个矩形,用$s[x_1][y_1][x_2][y_2]$表示坐标组围成的矩形的数值的平方,用$d[k][x_1][y_1][x_2][y_2]$表示棋盘被分为$k$个矩形时坐标组围成的矩形的数值的平方和的最小值。 那么状态转移方程为

$$d[k][x_1][y_1][x_2][y_2]=min\begin{cases} min_{x_1\le x<x_2}\begin{cases} d[k-1][x_1][y_1][x][y_2]+s[x+1][y_1][x_2][y_2] & \text{进行上下分割,取上方的矩形继续分割}\\ d[k-1][x+1][y_1][x_2][y_2]+s[x_1][y_1][x][y_2] & \text{进行上下分割,取下方的矩形继续分割} \end{cases} \\ min_{y_1\le y<y_2}\begin{cases} d[k-1][x_1][y_1][x_2][y]+s[x_1][y+1][x_2][y_2] & \text{进行左右分割,取左边的矩形继续分割}\\ d[k-1][x_1][y+1][x_2][y_2]+s[x_1][y_1][x_2][y] & \text{进行左右分割,取右边的矩形继续分割} \end{cases} \end{cases}$$

我们所要求的即为$d[n][1][1][8][8]$,由于棋盘大小给定,只有$n$未知,那么时间复杂度为$O(8^4\centerdot n)$
View Code in Github Repository

HDOJ-1159
题目:求两个字符串序列的最长公共子序列(Longest Common Sequence) 思路:经典的dp问题,最优子结构的状态转移方程是 $$c[i][j]= \begin{cases} c[i-1][j-1]+1 & \text{if $x[i]=y[j]$}\\ max(c[i-1][j],c[i][j-1]) & \text{if $x[i]\not=y[j]$} \end{cases}$$

其中$c[i][j]$表示串$x$的前$i$个字符和串$y$的前$j$个字符的LCS。 重叠子问题在于$i$和$j$的取值范围有限,假设$x.length=m,y.length=n$,那么他们的公共子序列只有$m\times n$种选择,如果直接进行递归求解,易得递归树的高度为$m+n$,那么时间复杂度将为指数级的$2^{m+n}$,通过自底向上计算并保存当前长度,即可得到结果,时间复杂度即为$O(mn)$
View Code in Github Repository

POJ-2533
题目:给出一个数字的序列,求它的最长上升子序列
思路:状态转移方程:

$$a[i]=max_{1\le k < i}(a[k])\ \ if\ v[i]>v[k]$$

其中$a[i]$表示包含前$i$个数的最长上升子序列的最大长度,$v[i]$表示第$i$个数的值
设序列长度为$n$,则时间复杂度为$O(n^2)$
View Code in Github Repository

POJ-1322
题目:一个袋子里有无穷多$c$种颜色的球,每个球取出的概率总是均等,如果取出的球中发现有两个球颜色相同,则将它们丢弃,求取出$n$个球后,留下的球的个数
思路:首先留下的球的个数不可能超过$c$个,也不可能超过$n$个,最优子结构的状态转移方程为

$$p[i][j]=p[i-1][j-1]\times (1-\frac{j-1}{c})+p[i-1][j+1]\times \frac{j+1}{c}$$

其中$p[i][j]$表示取出$i$个球后,留下的球为$j$个的概率,方程也表示出了两种可能,即在取出$i-1$个球的时候,留下的球为$j-1$和$j+1$个的概率。这里要注意由于$n$最大为$10^6$,所以直接开数组会爆掉空间,使用滚动数组来做;还要注意由于颜色最多为$10^2$种,所以在取若干次之后,在误差允许的范围下得到的留下各种球的概率是相同的(不知道怎么证明...100种颜色在500次的时候已经看不出差别了),设立一个eps值,当两次误差小于该值时直接输出即可,不用真正取很多次,还有奇偶性方面,$i+j$的值不可能为奇数,这一点也可以提高常数级的效率。
View Code in Github Repository