三角形求最大和的问题

[问答题]

题目标题：

三角形求最大和的问题

题目描述：

如图所示是一个由数字组成的三角形，编写程序按照某条路线遍历从第一行的首数字到最后一行的某个数，使每一行经过的数字相加的和为最大值，每一次跳转可以向左下方或者右下方进行。例如样图中第一行为7,选择左下方的数字3的话，继续选择左下方的数字8，第四行选择右下方的7，最后到达左下方的数字5。这样，7+3+8+7+5=30为最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

输入描述：

先由键盘输入三角形的行数N(1

输出描述：

输出计算出的数字相加和的最大值。

样式输入：

3 8

8 1 0

2 7 4 4

4 5 2 6 5

样式输出：

7184

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
vector<vector<int> > dp(n,vector<int> (n));
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
cin>>dp[i][j];
}
}
for(int i=n-2;i>=0;i--)
{
for(int j=0;j<=i;j++)
{
dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
}
}
cout<<dp[0][0]<<endl;
}
return 0;
}

发表于 2018-01-05 10:42:33 回复(0)

阿奻_

#include<stdio.h>
int main()
{
int a[100][100];
int i,j,n;
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<i+1;j++)
scanf("%d",&a[i][j]);
for(i=n-2;i>=0;i--)
for(j=0;j<i+1;j++)
a[i][j]+=a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1];
printf("%d",a[0][0]);
return 0;
}