数字三角形:
给定一个由 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;
}