【题目描述】

给字一个由n行数字组成的数字三角形（等腰三角形）。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

【输入描述】

数字三角形的行数和数字三角形

【输出描述】

最大的路径和

【样例输入1】

5  7  8 3  9 8 7  1 2 3 4  4 5 6 7 8

【样例输出1】

33

【样例输入2】

5  7  3 8  8 1 0  2 7 4 4  4 5 2 6 5

【样例输出2】

30

【样例解释】

对于样例1，路径是7 8  8 3 7

【题目分析】

1. 从输入的角度看，第一行一个数，第二行两个数，第三行三个数，依次类推（类似九九乘法表那种）。

2. 典型的”动态规划“类型问题。需要用到递归的思想

3. 需要推导出"状态转移方程"

   
   
   

   
   
   

【参考答案1】——递归思路

用二维数组Ｄ来存放数字三角形，问题转换如下：

D(i，j)：表示第 i 行第 j 列的数字。（i，j从0开始）

Sum(i，j)：表示从 D(i，j) 到底边的最优解，即：从 D(i，j) 到底边的各条路径中，数字之和最大的一个。

问题：求 Sum(0,0)。即：第0行第0列到底边的路径的最大和。

当只有一行时，它的最大路径和就是它本身。

即：Sum(i,j) =D(i,j)

其次，它的最大路径和就是它本身加上它下面左右两个元素的最大路径和的较大者。因为是使用二维数组来存数字，就是它本身加上他正下方和他右下方两个元素的最大路径和的较大者。

即：Sum(i,j) =max{Sum(i+1,j)，Sum(i+1，j+1)}+D(i，j)

写出递归方程：

然后根据递归方程

#include<iostream>  using namespace std;  const int N = 100;  int D[N][N];  int max(int a, int b)  {  	int m = a > b ? a : b;  	return m;  }  int fun_d(int i,int j,int n)  {  	if (i == n-1)  		return D[i][j];  	int Sum_L = fun_d(i + 1, j, n);  	int Sum_R = fun_d(i + 1, j + 1, n);  	return max(Sum_L, Sum_R)+D[i][j];    }  int main()  {  	int n, i, j;    	cin >> n;//n行数  	for (i = 0; i < n; i++)  	{  		for (j = 0; j <= i; j++)  		{  			cin >> D[i][j];  		}  	}  	int MaxSum = fun_d(0,0,n);  	cout << MaxSum << endl;  	return 0;  }

【参考答案2】

#include <iostream>  #include <algorithm>  using namespace std;  #define MAX 101  int n;  int D[MAX][MAX];  int maxSum[MAX][MAX];    int main()  {      int i,j;      cin >> n;      for(i = 1;i <= n;i++)          for(j = 1;j <= i;j++)              cin >> D[i][j];            for( int i = 1;i <= n; ++ i )          maxSum[n][i] = D[n][i];//最后一行的值正好就等于D的最后一行的值            for( int i = n-1; i >= 1; --i )//从n-1行向上一直推到第一行          for( int j = 1; j <= i; ++j )//对于每一行我们要从左到右求出每一个数字的最大和              maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j];                    cout << maxSum[1][1] << endl;  }

(adsbygoogle = window.adsbygoogle || []).push({});