数字三角形:

给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下),使该路径经过的数字总和最大。

输入格式:

输入有n+1行:

第 1 行是数字三角形的行数 n,1<=n<=100。

接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。

输出格式:

输出最大路径的值。

输入样例:

在这里给出一组输入。例如:

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

输出样例:

在这里给出相应的输出。例如:

30

题意:中文题也挺好理解,就不解释了。

题解:偷偷告诉大家,这题是我看我女朋友没做出来才写的。        自我感觉这个题比较像求前缀和,就是求出所有路径的和排序就好了,不过每次都加上一次可以加的最大的那个数,详细请看代码。

#include <iostream>
using namespace std;
int dp[400][400];
int a[400][400];
int main(){
	int n;
	cin >> n;
	for (int i = 1; i <= n;i++){
		for (int j = 1; j <= i;j++){
			cin >> a[i][j];
		}
	}// 输入数字三角形 ,从1开始输入是因为下面,待会儿解释。
	int ans=0;
	for (int i = 1; i <= n ;i++){
		for (int j = 1; j <= i;j++){
			dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
		}
	}
    // 因为只能斜着走,也就是这里的j和j-1每次加上其中最大的那个,当然是加的上一行,即i-1行。
   // 从1开始输入,这样保证dp[i-1][j-1],dp[i-1][j]中的下标不会小于零。
	int max=-1;
	for (int i = 1; i <= n;i++){
		if(dp[n][i]>max){
			max=dp[n][i];
		}
	}// 求出了最后一行,每个数对应的最大的和,然后再找一个这里面最大的,就可以了。
	cout << max << endl;
	return 0;
}