数字三角形 dp

2017年02月24日 9点热度 0人点赞 0条评论
问题描述
  (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
  径,使该路径所经过的数字的总和最大。
  ●每一步可沿左斜线向下或右斜线向下走;
  ●1<三角形行数≤100;
  ●三角形中的数字为整数0,1,…99;

  数字三角形 dp.
  (图3.1-1)

输入格式
  文件中首先读到的是三角形的行数。

  接下来描述整个三角形

输出格式
  最大总和(整数)
样例输入
5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5
样例输出

30

代码

#include
#include
using namespace std;
int main(){
int a[160][160],i,j,n;
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&a[i][j]);
for(j=n-1;j>=1;j--)
for(i=1;i<=j;i++)
a[j][i]+=max(a[j+1][i],a[j+1][i+1]);
cout<return 0;
}

未经允许不得转载!数字三角形 dp

update

纸上得来终觉浅, 绝知此事须躬行。