数字三角形问题

3-4数字三角形问题

一、问题描述：给定一个由n行数字组成的数字三角形，如下图所示。试设计一个算法，计算出从三角形顶至底的一条路径，使得该路径经过的数字之和最大。

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

二、算法设计：

对于给定由n行数字组成的数字三角形，计算出从三角形顶至底的路径经过的数字之和最大。

三、思路分析：

用动态规划，下两个数与上一个数分别相加，取大的数置于上个数的位置：例如一二行，3+7与7+8取7+8=15置于7的位置

四、代码实现：

#include

int a[20][20];

int i,j,k,sum=0;

int exchange(int &a,int &b)

{

return (a>b?a:b);

}

void main()

{

cout<<"输入n(三角形的行数)"<

cin>>k;

cout<<"输入数字三角形"<

for(i=0;i

for(j=0;j<=i;j++)

{

cin>>a[i][j];

}

for(i=k-1;i>=0;i--)

{

for(j=i;j>=0;j--)

{

int n,m;

n=a[i][j]+a[i-1][j-1];

m=a[i][j-1]+a[i-1][j-1];

a[i-1][j-1]=exchange(n,m);

}

}

cout<

}

五、运行截图：

六、总结：

首先通过对数字三角形的问题分析，找到了最优子结构的性质，紧接着建立动态规划方程，并予以求解，最终通过代码实现方程，最后对复杂度简要分析得O(n^2)。