Chris

看了《算法导论》上对动态规划的讲解，觉得自己对动态规划的理解又进了一步，之前在读到《算法之道》相关章节时就有这感觉，但是仍然不敢说自己已经完全掌握了动态规划，只是比以前又透彻了一些，说说自己新的理解，其实就是复述一下算法导论上的内容而已。

0.两个例子

装配线调度问题

一个产品要经过N道工序，有两条装配链提供着N道工序，在任何一道工序i时产品都可以选择在两条线上的一条进行加工，在装配线1上加工工序i的时间 为a[i][1]，装配线2上类似。在同一条装配线上前进不花时间，跳转到另一条装配线上需要一定的时间t[1][i]（从装配线1的工序i跳转到装配线 2的工序i+1所花费的时间）和t[2][i]（类似）。

问题是求解一个产品最快完成所有工序所需的时间。

动态规划解法：

我们用dp[i][j]存放在第j条装配线完成第i到工序所用的最少时间，其中i=1…N,j=1,2。因为要么是从同条装配线的上一道工序而 来，要么是从另一条装配线的上一道工序跳转而来，而最少时间应该是这两种情况里较少的那种。注意应该认为dp[i-1][1]和dp[i-1][2]已经 求解完毕，或者说不要关心它们，只要认为它们存放的是正确答案就可以了，为何可以如此，见后面。则有：

dp[i][1] = min(dp[i-1][1]+a[i][1],dp[i-1][2]+t[i-1][2]+a[i][1])

dp[i][2] = min(dp[i-1][1]+t[i-1][1]+a[i][2],dp[i-1][2]+a[i][2])

这样min(dp[N][1],dp[N][2])就是想要的答案。

矩阵链乘法问题

两个矩阵A(lxm)*B(mxn)相乘所需要的代价是O(lmn)，而相乘得到的矩阵式C(lxn)型的，l和n作为矩阵的行列数量仍然保存在了 矩阵链中，因此对于一个矩阵链的乘法来说，做乘法的顺序不同，所花费的时间就可能相差很多，矩阵链乘法问题就是对于一个给定的矩阵链相乘，求解最少的计算 时间（如何安排乘法的计算顺序）。

动态规划解法：

我们用dp[i][j]表示矩阵链中从第i个乘到第j个所需的最少时间，用r[i]和c[i]分别表示第i个矩阵的行数和列数。有：

dp[i][j]=min(k)(dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j])

注意c[k]==r[k+1]

即，i到j这一部分矩阵链的最优计算一定是在某处k（i<=k<j）将矩阵链分成两部分，通过先计算i到k和k+1到j这两条矩阵链再将这两个矩阵相乘得到的。

1.什么是动态规划

dynamic programming这里的programming指的是查表，表里存放的是之前求解过的子问题的解。动态规划就是动态查表，即在求解的过程中的每一步 都需要查表来得到对当前子问题求解所需的信息。如在装配线问题上dp[i][1]就分别查表找到了dp[i-1][1]和dp[i-1][2]；矩阵乘法 链问题上dp[i][j]的求解查表找到了对应于不同k值的dp[i][k]和dp[k+1][j]。

正因为存放在了表里，所以不用再次求解，才达到了较高的效率，将传统回溯解法指数的复杂度降低为多项式程度，关于复杂度后面还会说到。

2.最优子结构

一个问题要想用动态规划的方法来解决，必须具有最优子结构，至于为什么具有最优子结构的问题就可以用动态规划来解决，后面说。现在说说什么叫最优子结构。

最优子结构是指一个问题的解是一个选择过程，可能是二选一（装配线问题选择从前一道工序的哪条线上过来）、可能是多选一（矩阵链决定从哪里断开，即 先做哪一处乘法）。假设作出了正确的选择后（这其实是需要子问题信息来做选择依据的），原问题就退化成一个或多个子问题（在装配线问题中，退化成所选择的 那条装配线上完成第i-1道工序需要的最少时间，这是一个子问题；在矩阵乘法链问题中，退化成两条矩阵链i到k和k+1到j的最优求解问题，这是两个子问 题），所谓子问题指的是与原问题同构但规模较小的问题。

光有这个性质还不叫具有最优子结构，最优子结构的另一个要求是原问题的最优解必须包含子问题的最优解。在验证这一点时，可以通过剪贴+反证法的思 路，即如果该解法用到的子问题的解不是最优的，那么以最优的解代替之一定可以得到该问题的一个更好的解。还是通过例子说，装配线问题中，不管加工工序i的 最优选择是从哪条线过来，所用到的在该线上加工工序i-1的时间一定需要是最优的，否则用最优的替换之可得到对于工序i的一个更优的解。

有了这两条性质——1.做选择后问题退化为一个或几个子问题、2.问题的最优解包含子问题的最优解，一个问题就具备了最优子结构。

3.为什么高效、如何求解

如果一个问题具有最优子结构的第一条性质，就可以使用分而治之的思想求解，比如递归。通常做法是将问题分解，然后对于分解出现的各个子问题分别递归求解，如果这种分解是多分枝的，那么复杂度应该是指数级的。

同递归思想一样，动态规划也需要对所有子问题都全部求解才能得到最终的答案，但是动态规划不愿意单纯地像递归那样做，而希望能够通过一些手段只做必要的工作，多余的一点都不想做。

动态规划是基于如下两点观察：

1）某个子问题的求解只和规模更小的子问题求解有关，而与与其同规模或者更大规模的子问题求解无关。

2）某个子问题的求解只用到其子问题的最优解，也就是说对于一个子问题来说，只有其最优解是有价值的。

通过观察1）我们知道只要在求解所有子问题时控制子问题的求解顺序按照子问题规模递增来进行，就能保证求解任意子问题时，它所依赖的规模较小的子问题都已经求解完毕。

通过观察2）我们知道只有最优解是有意义的，因此我们将最优解存在表里以供后面用到时查找，就可以保证某个子问题只被求解一遍，而且有了上一个观察，在求解某个子问题时，可以保证它所需要的表格内容都已经准备好了。

所以动态规划的解法已经呼之欲出了。

首先证明一个问题具有最优子结构，然后发现描述该问题的子问题应该是什么形式的（装配线问题中的dp[i][1]、dp[i][2]和矩阵链乘法问题中的dp[i][j]），按照子问题规模递增的顺序求解所有子问题，最后得到整个问题的解。

而，这里的关键就是找出子问题的形式，和子问题在经过选择后如何向更小规模的子问题退化。

下面给出两个例子的伪代码

装配线问题

dp[1][1] = a[1][1];
dp[1][2] = a[1][2];
for (int i = 2;i <= n;i++)
{
	dp[i][1] = min(dp[i-1][1]+a[i][1],dp[i-1][2]+t[i-1][2]+a[i][1]);
	dp[i][2] = min(dp[i-1][1]+t[i-1][1]+a[i][2],dp[i-1][2]+a[i][2]);
}

矩阵链乘法

for (int i = 1;i <= n;i++)
{
	dp[i][i] = 0;
}
for (int l = 2;l <= n;l++)
{
	for (int i = 1;i <= n-l;i++)
	{
		int j = i+l-1;
		for (int k = i;k < j;k++)
		{
			dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j]);
		}
	}
}

4.动态规划的时间复杂度由什么决定

动态规划的过程就是求解所有子问题的过程，因此首先复杂度由子问题的个数决定，而子问题的个数又有子问题的形式所决定。在装配线问题中子问题形式是 dp[i][1 or 2]，其中只有i是变化的，因此子问题个数为O(n)；在矩阵链乘法问题中，子问题形式是dp[i][j]，i和j都在变化，因此子问题个数是 O(n^2)。另外由于前面所提到的每一个子问题都是一个选择，可能是二选一，可能是多选一，而要解答此子问题就要考察所有的选项，因此每一个子问题的求 解时间还和面临的选择个数有关，因此复杂度应该是子问题个数*每个子问题面临选择数。这样，装配线问题的时间复杂度O(n)，矩阵链乘法问题的时间复杂度 为O(n^3)，正如代码中所示。

Description

Input

Output

Sample Input

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

Sample Output

15

Source

#include <iostream>
 
using namespace std;
 
int numbers[105][105],dp[105],n,temp[105];
 
int main()
{
	cin>>n;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= n;j++)
			cin>>numbers[i][j];
	int Max = 0;
	for (int i = 1;i <= n;i++)	//start from line i
	{
		memset(temp,0,sizeof(temp));
		for (int j = i;j <= n;j++)	//end at line j
		{
			for (int k = 1;k <= n;k++)
			{
				temp[k] += numbers[j][k];
 
				if (temp[k] + dp[k-1] > 0)
					dp[k] = temp[k] + dp[k-1];
				else
					dp[k] = 0;
 
				if (Max < dp[k])
					Max = dp[k];
			}
		}
	}
	cout<<Max<<endl;
}

Description

‘Oh no, they’ve done it again’, cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross each other all over the place. At this late stage of the process, it is too expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without crossing each other, is imminent. Bearing in mind that there may be thousands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?

A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number specifies which port on the right side should be connected to the i:th port on the left side.Two signals cross if and only if the straight lines connecting the two ports of each pair do.

Input

Output

Continue reading »

Description

“Help Jimmy” 是在下图所示的场景上完成的游戏。

场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。

Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。

设计一个程序，计算Jimmy到底地面时可能的最早时间。

Input

1
3 8 17 20
0 10 8
0 10 13
4 14 3

23

if (板子i的左侧下方Max以内的距离有其它板子j)
	f[i].fromLeft=i高度-j高度+max(i的X走到j左侧的时间+f[j].fromLeft,i的X走到j右侧的时间+f[j].fromRight);
else
	f[i].fromLeft=正无穷;

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
#define INF 9999999
 
struct _platform 
{
	int x1;
	int x2;
	int height;
};
 
bool UDgreater(_platform p1,_platform p2)
{
	return p1.height < p2.height;
}
 
struct _time
{
	int fromLeft;
	int fromRight;
};
 
int N,X,Y,MAX;
vector<_platform> pvec;
_time fastest[1005];
 
void prepare()
{
	memset(fastest,INF,sizeof(fastest));
	pvec.clear();
	cin>>N>>X>>Y>>MAX;
 
	_platform platform;
	platform.x1 = -INF;
	platform.x2 = INF;
	platform.height = 0;
	pvec.push_back(platform);
 
	for (int i = 1;i <= N;i++)
	{
		cin>>platform.x1>>platform.x2>>platform.height;
		if (platform.height <= Y)
		{
			pvec.push_back(platform);
		}
	}
	platform.x1 = X;
	platform.x2 = X;
	platform.height = Y;
	pvec.push_back(platform);
	sort(pvec.begin(),pvec.end(),UDgreater);
}
 
bool CanLoad(int i,int j,int dir)
{	//whether Jimmy can load on j from i safely;0 for left,1 for right
	if (dir == 0)
	{
		if (pvec[i].height-pvec[j].height <= MAX&&\
			pvec[i].x1>=pvec[j].x1&&pvec[i].x1<=pvec[j].x2)
			return true;
	}
	else
	{
		if (pvec[i].height-pvec[j].height <= MAX&&\
			pvec[i].x2>=pvec[j].x1&&pvec[i].x2<=pvec[j].x2)
			return true;		
	}
	return false;
}
 
int main()
{
	int n;
	cin>>n;
	while (n--)
	{
		prepare();
		fastest[0].fromLeft = 0;
		fastest[0].fromRight = 0;
		int size = pvec.size();
		for (int i = 1;i < size;i++)
		{
			int leftMin = INF,rightMin = INF;
			int j = i-1;
			while(j>=0&&!CanLoad(i,j,0))
				j--;
			if (j > 0)
				fastest[i].fromLeft = min(fastest[j].fromLeft+\
				abs(pvec[i].x1-pvec[j].x1),fastest[j].fromRight+\
				abs(pvec[i].x1-pvec[j].x2))+abs(pvec[i].height-pvec[j].height);
			else if(j == 0)
				fastest[i].fromLeft = abs(pvec[i].height-pvec[j].height);
			j = i-1;
			while (j>=0&&!CanLoad(i,j,1))
				j--;
			if (j > 0)
				fastest[i].fromRight = min(fastest[j].fromLeft+\
				abs(pvec[i].x2-pvec[j].x1),fastest[j].fromRight+\
				abs(pvec[i].x2-pvec[j].x2))+abs(pvec[i].height-pvec[j].height);				
			else if(j == 0)
				fastest[i].fromRight = abs(pvec[i].height-pvec[j].height);
		}
		cout<<min(fastest[size-1].fromLeft,fastest[size-1].fromRight)<<endl;
	}
}