A48217. 数字三角形问题上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。输入输入的是一行是一个整数N (1 N = 100)给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间输出输出最大的和。样例…
填空题
较难
知识点
题目描述
数字三角形问题
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。
输入
输入的是一行是一个整数N (1 N = 100)给出三角形的行数。下面的N行给出数字三角形。
数字三角形上的数的范围都在0和100之间
输出
输出最大的和。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
参考答案
#define MAX 100
#define getMax(x,y) (x>y ? x : y)
#include <stdio.h>
void main(void)
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
//初始化数组的元素全部为0
int path[MAX][MAX] = {0};
int dist[MAX][MAX] = {0};
//为三角形赋值
int i = 0;
int j = 0;
int n = 0; //三角形的行数
scanf("%d", &n);
for(i= 0; i < n; i++)
{
for(j = 0; j <= i; j++)
{
scanf("%d", &path[i][j]);
}
}//for
//为了防止转移方程越界，每行的开头和结尾首先算出最长路径
dist[0][0] = path[0][0];
for(i = 1; i < n; i++)
{
dist[i][0] = dist[i-1][0] + path[i][0];
}//for
for(i = 1; i < n; i++)
{
dist[i][i] = dist[i-1][i-1] + path[i][i];
}
//计算出中间每个节点的最长路径
for(i = 2; i < n; i++)
{
for(j = 1; j < i; j++)
{
dist[i][j] = getMax(dist[i-1][j-1], dist[i-1][j]) + path[i][j];
}
}
//找到最长的路径
int maxSum = 0;
for(j = 0; j < n; j++)
{
if(maxSum < dist[n-1][j])
{
maxSum = dist[n-1][j];
}
}//for
printf("%d", maxSum);
fclose(stdin);
fclose(stdout);
return;
}
上一题
下一题