算法设计与分析 动态规划 习题

习题"/>

算法设计与分析 动态规划 习题

3.1

满足递归式F(n)=F(n-1)+F(n-2)和初始值F(0)=F(1)=1的数列称为斐波那契数列。考虑如何计算该数列的第n项F(n)。

（1）说明根据递归式直接完成计算，将有子问题重复求解；
（2）说明该问题具有优化子结构；
（3）写出求解F(n)的动态规划算法，并分析算法的时间复杂性。

• O(logN)求斐波那契数列第N项：动态规划、矩阵分治

3.2

数字三角形问题：设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示：

要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。

要求：(1) 写出递推方程；(2)写出算法伪代码；(3) 分析算法的时间复杂度。

• 解法：从底向上递推， f ( i ) ( j ) = M A X [ f ( i − 1 ) ( j ) , f ( i − 1 ) ( j + 1 ) ] f(i)(j)=MAX[f(i-1)(j), f(i-1)(j+1)] f(i)(j)=MAX[f(i−1)(j),f(i−1)(j+1)]
• 复杂度 O ( n ) O(n) O(n)

for (int i=n-1;i>=1;i--){for (int j=1;j<=i;j++){f[i][j]=max(f[i-1][j], f[i-1][j+1]);}
}

3.3

给定一个n×n的矩阵 A，矩阵中的元素只取 0 或者 1。设计一个动态规划算法，求解得到 A 中元素全是 1 的子方阵使其阶数达到最大值。

要求写出伪代码、递归方程并分析算法的时间复杂度。

• 解法： f ( i ) ( j ) f(i)(j) f(i)(j)表示以第 i i i行 j j j列的格子为矩阵右下角的阶数最大值
• f ( i ) ( j ) = M I N ( f ( i − 1 ) ( j − 1 ) , k ) + 1 f(i)(j)=MIN(f(i-1)(j-1), k)+1 f(i)(j)=MIN(f(i−1)(j−1),k)+1
• 满足 a [ i ] [ j − h ] = a [ i − h ] [ j ] , h = 0 , 1 , 2 , . . . , k a[i][j-h]=a[i-h][j], h=0,1,2,...,k a[i][j−h]=a[i−h][j],h=0,1,2,...,k且 k k k最大

3.4

石子归并问题：在一个圆形操场的四周摆放着n堆石子，现要将石子有次序地合并成一堆。规定每次只能选择相邻的两堆石子合并成新的一堆，并将新一堆石子数记为该次合并的得分。试设计一个动态规划算法，计算出将n堆石子合并成一堆的最小得分和最大得分.

要求列出递归方程，写出算法的伪代码并分析算法的计算复杂性。

• 解法：分别使用最大堆和最小堆，每次取出两次堆顶元素，合并，计算代价，再放入堆中。

3.5

我们考虑将数轴上的n个点聚成k类的问题。
输入：n个从小到大的不同实数x1, x2, …, xn表示n个不同点，一个参数kn.
任务：将n个点划分成k个不相交的非空集合S1, …., Sk满足⋃_(i=1)^k▒S_i ={x1, x2, …, xn}，Si中所有点在Si+1中所有点左边，1i<k，也就是说对于任意xSi, zSi+1, y<z.

目标：最小化∑_(i=1)^k▒〖cost(S_i)〗,其中cost(Si)=(max(Si)-min(Si))2. max(Si)是Si中的最小元素，min(Si)是Si中的最大元素。

例如，如果Si={xj}，cost(Si)=0，如果Si={xj, xj+1, …, xj+t}, xj,<xj+1< …< xj+t，那么cost(Si)=(xj+t-xj)2.

• 思路：猜想代价单调且满足贪心策略（未证明，不确定）
• 大概像下一题3.6一样，代价计算策略不同

3.6

假设书架上一共有9本书，每本书各有一定的页数，分配3个人来进行阅读。为了便于管理，分配时，各书要求保持连续，比如第1、2、3本书分配给第1人，4、5分配给第二人，6，7，8，9分配给第3人，但不能1，4，2分配给第1人，3，5，6分配给第2人。即用两个隔板插入8个空隙中将9本书分成3部分，书不能换位。同时，分配时必须整本分配，同一本书不能拆成两部分分给两个人。为了公平起见，需要将工作量最大的那一部分最小化，请设计一个动态规划算法。用s1,…,sn表示各本书的页数。

（1）简明的写出问题的递推方程； （2）描述算法伪代码； （3）分析算法的时间复杂度。

• 解法： f ( i , j ) f(i, j) f(i,j)为从第1到第i本书分为j份的最小最大值
• 前提：因为一堆书被分为k-1份后，再分一份变成k份一定更优
• f ( i , j ) = M I N [ M A X [ f ( p , i − 1 ) + s u m [ j ] − s u m [ p ] ] ] , p = i , i + 2 , . . . j − 1 , s u m [ i ] = s i g m a ( 1 , i ) f(i, j)=MIN[MAX[f(p, i-1)+sum[j]-sum[p]]], p=i,i+2,...j-1, sum[i]=sigma(1,i) f(i,j)=MIN[MAX[f(p,i−1)+sum[j]−sum[p]]],p=i,i+2,...j−1,sum[i]=sigma(1,i)

3.7

将一根木棒折成若干份，每折一次的代价是当前这段木棒的长度, 总代价是折这根木棒直到满足要求所需要的所有操作的代价。例如，将一根长度为10的木棒折成四段，长度分别为2, 2, 3, 3，如果先折成长度为2和8的两段，再将长度为8的折成长度为2和6的两段，最后将长度为6的折成长度为3的两段，这些操作的代价是10+8+6=24；如果先折成长度为4和6的两段，在分别将长度为4的折成长度为2的两段、长度为6的折成长度为3的两段，则这些操作的代价是10+4+6=20，比上一种方案更好一些。该问题的输入是木棒的长度L和一些整数c1,…,cn,.

要求将木棒折成长度为c1, …, cn的n段且操作代价最小，请设计动态规划算法解决该问题。

• 解法：逆向3.4