数字三角形

上面给出了一个数字三角形，从三角形的顶部到底部有多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，累加和最大的路径称为“最佳路径”。题目的任务就是求出最佳路径上的数字之和。

注意：路径上的每一步只能从一个数走到下一层和它最近的左边的数或者右边的数。

解题思路（分治法）：用递归的方法解决。基本思路是：以D( r , j )表示第r行第j个数字（ r , j 都从1开始算），以MaxSum( r , j )代表从第r行的第j个数字到底边的最佳路径的数字之和，则本题目要求MaxSum( 1 , 1 )。

         从某个D( r , j )出发，显然下一步只能走D ( r+1 , j )或D ( r+1 , j+1 )。如果走D ( r+1 , j ),那么得到的MaxSum( r , j )就是MaxSum( r+1 , j )+D( r , j )；如果走D ( r+1 , j +1),那么得到的MaxSum( r , j )就是MaxSum( r+1 , j +1)+D( r , j ）。所以选择往哪里走，就需要比较MaxSum（r+1,j）和MaxSum（r+1，j+1）哪个值更大。

参考程序：

#include<iostream>
#include<cstdio>
using namespace std;
 
#define MAX_NUM 100
int d[MAX_NUM+10][MAX_NUM+10];
int N;
 
int MaxSum(int r,int j)  //递归求解最大路径和 
{
	if(r==N)
		return d[r][j];
	int sum1=MaxSum(r+1,j);
	int sum2=MaxSum(r+1,j+1);
	if(sum1>sum2)
		return sum1+d[r][j];
	return sum2+d[r][j];
}
 
int main()
{
	int m;
	cin>>N;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=i;j++)
			cin>>d[i][j];
	cout<<MaxSum(1,1);
	return 0;
}

分析上面的程序，细心的人会发现存在大量的重复计算子问题，因此，我们采用动态规划的记录子问题的方法再来完善一下程序。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
#define MAX_NUM 100
int d[MAX_NUM+10][MAX_NUM+10];
int N;
int maxSum[MAX_NUM+10][MAX_NUM+10];   //maxSum[i][j]用于保存第i行第j列的最优值 
 
int MaxSum(int r,int j)  //递推求解最大路径和 
{
	if(r==N)
		return d[r][j];
	if(maxSum[r+1][j]==-1)   //如果MaxSum(r+1,j)没有计算过,计算后保存 
		maxSum[r+1][j]=MaxSum(r+1,j);
	if(maxSum[r+1][j+1]==-1)   //如果MaxSum(r+1,j+1)没有计算过,计算后保存 
		maxSum[r+1][j+1]=MaxSum(r+1,j+1);
	if(maxSum[r+1][j]>maxSum[r+1][j+1])
		return maxSum[r+1][j]+d[r][j];
	return maxSum[r+1][j+1]+d[r][j];
}
 
int main()
{
	int m;
	cin>>N;
	//将maxSum全部置成-1，表示开始所有的MaxSum(i,j)都没有计算过
	memset(maxSum,-1,sizeof(maxSum)); 
	for(int i=1;i<=N;i++)
		for(int j=1;j<=i;j++)
			cin>>d[i][j];
	cout<<MaxSum(1,1);
	return 0;
} 

从上面可以得出动态规划的基本思想：将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，可以称为“动态规划”。动态规划通常用来求最优解。      能用动态规划解决的求最优解问题，必须满足最优解的每个局部解也都是最优的。以上题为例，最佳路径中的每个数字到底部的那一段路径，都是从该数字出发到底部的最佳路径。

实际上，递归的思想在编程时未必要实现为递归函数。在尚明的例子中，有递推公式

MaxSum( r  , j ) = d( r , j ) ,当且仅当 r = N ；MaxSum（ r , j ）= Max { MaxSum( r+1 , j ) , MaxSum( r+1 , j+1 ) } + d ( r , j ) , 其他；

不需要写递归函数，从maxSum[ N -1 ]这一行元素开始向上逐行递推，就能求得最终maxSum[ 1 ][ 1 ]的值。程序如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
#define MAX_NUM 100
int d[MAX_NUM+10][MAX_NUM+10];
int N;
int maxSum[MAX_NUM+10][MAX_NUM+10];   //maxSum[i][j]用于保存第i行第j列的最优值 
 
int main()
{
	int i,j;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
		for(j=1;j<=i;j++)
			scanf("%d",&d[i][j]);
	for(j=1;j<=N;j++)
		maxSum[N][j]=d[N][j];
	for(i=N;i>1;i--)
		for(j=1;j<i;j++)
		{
			if(maxSum[i][j]>maxSum[i][j+1])
				maxSum[i-1][j]=maxSum[i][j]+d[i-1][j];
			else
				maxSum[i-1][j]=maxSum[i][j+1]+d[i-1][j];
		}
	printf("%d\n",maxSum[1][1]);
	return 0;
}
 

到这就是动态规划思想的全部展现，还不是很清楚的可以参看 动态规划思想。但是，就本题目还有一个问题就是需要一个二维数组还存放中间值，所以，下面还有一个巧妙的思想来节省空间。

实际上，因为maxSum[ i ][ j ]的值在用来计算出maxSum[ i-1 ][ j ]后已经无用，所以可以将计算出的maxSum[N-1][ 1]替换原来的maxSum[N][1],计算出maxSum[N-1][2]替换原来的maxSum[N][2]……计算出maxSum[n-1][n-1]替换原来的maxSum[n][n-1],maxSum数组实际上只用最后一行，就能够存放上面程序中本该存放在maxSum[n-1]那一行的全部结果。同理，再一行行向上递推，maxSum数组只需要最后一行就可以存放全部中间计算结果，最终的结果（本该是maxSum[1][1]）也可以存放在maxSum[n][1].因此，实际上maxSum不需要是二维数组，一维数组就足够了。改写程序如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
 
#define MAX_NUM 100
int d[MAX_NUM+10][MAX_NUM+10];
int N;
int *maxSum; 
 
int main()
{
	int i,j;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
		for(j=1;j<=i;j++)
			scanf("%d",&d[i][j]);
	maxSum=d[N];   //maxSum指向第n行 
	for(i=N-1;i>=1;i--)
		for(j=1;j<=i;j++)
			maxSum[j]=max(maxSum[j],maxSum[j+1])+d[i][j]; 
	printf("%d\n",maxSum[1]);
	return 0;
}
 

这种用一维数组取代二维数组进行递推、节省空间的技巧叫“滚动数组”。上面的程序虽然节省了空间，但是没有降低时间复杂度。