【算法设计与分析】数字三角形问题——对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。_给定一个由 n 行数字组成的数字三角形,试设计一个算法,计算出 从三角形的顶至底的

一、问题描述

  给定一个由n行数字组成的数字三角形，试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
数据输入： 由文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，(1≤n≤100)。接下来n行是数字三角形各行中的数字。所有数字在0~99之间。
结果输出： 将计算结果输出到文件output.txt。文件第1行中的数是计算出的最大值。

二、分析

  用动态规划的方法自底向上计算。
  例如，输入如下数字三角形中的各行数字，具体步骤如下：

  根据上述步骤写出代码，运行结果如下，其中第1行为数字三角形的行数，接下来的5行是数字三角形各行中的数字。

三、运行结果

  运行程序后，打开output.txt文本，文件第1行中的数是计算出的最大值。

四、代码

#include<iostream>
#include<fstream>
using namespace std;
int a[100][100];
int main() {
	ifstream in("input.txt");
	ofstream out("output.txt");
	int n;
	in >> n;//n行数字
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= i; j++)
			in >> a[i][j]; //输入每行数字
	for (int i = n - 2; i >= 0; i--) { //自底向上
		for (int j = 0; j <= i; j++) {
			a[i][j] = max(a[i][j] + a[i + 1][j], a[i][j] + a[i + 1][j + 1]);
		}
	}
	out << a[0][0];
	in.close();
	out.close();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22