内容简介：题目：数字三角形题目介绍：如图所示的数字三角形，要求从最上方顶点开始一步一步下到最底层，每一步必须下一层，求出所经过的数字的最大和。
题目：数字三角形
题目介绍：如图所示的数字三角形，要求从最上方顶点开始一步一步下到最底层，每一步必须下一层，求出所经过的数字的最大和。
输入：第一行值n，代表n行数值；后面的n行数据代表每一行的数字。
输出：经过数字的最大和。
例：
输入：
4
1
3 2
4 10 1
4 3 2 20
输出：
24
分析：这也是一个典型的贪心算法无法解决的问题，同样可以用动态规划（dp算法）来解决。把边界数字首先初始化到结果矩阵中，再根据状态方程完成结果矩阵的遍历。需要注意的就是数组不是矩形而是三角形，与传统的状态方程相比需要做点改进。
数组编号：
状态方程：p[ i ][ j ]=max{ p[ i-1 ][ j-1 ] , p[ i-1 ][ j ]}
代码如下：
#include <iostream>
using namespace std;
int main()
{
int i;
int n;
cin >> n;
int **p = new int *[n];
for (i = 0; i < n; i++)
{
p[i] = new int[n];
}
for (i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
cin >> p[i][j];
}
}
for (i = 1; i < n; i++)
{
p[i][0] += p[i - 1][0];
}
for (i = 1; i < n; i++)
{
p[i][i] += p[i - 1][i - 1];
}
for (i = 2; i < n; i++)
{
for (int j = 1; j < i; j++)
{
p[i][j] += (p[i - 1][j - 1] > p[i - 1][j]) ? p[i - 1][j - 1] : p[i - 1][j];
}
}
for (i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
cout << p[i][j] << " ";
}
cout << endl;
}
}
结果如下图：
所以最下层的数字和最大值是24.
Linux公社的RSS地址： https://www.linuxidc.com/rssFeed.aspx
本文永久更新链接地址： https://www.linuxidc.com/Linux/2018-09/153946.htm
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
删除
[英] 维克托•迈尔-舍恩伯格（Viktor Mayer-Schönberger）著 / 袁杰 译 / 浙江人民出版社 / 2013-1 / 49.90元
《删除》讲述了遗忘的美德，为读者展现了大数据时代的取舍之道。 《删除》从大数据时代信息取舍的目的和方法分别诠释了“被遗忘的权利”。维克托首先回溯了人类追寻记忆的过程，之后提出数字技术与全球网络正在瓦解我们天生的遗忘能力。对此，他考察了促进遗忘终止4大驱动力——数字化，廉价的存储器，易于提取，全球性访问。之后，他提出了当前数字化记忆的两大威胁——信息权力与时间，并给出了应对威胁的6大对策——数......一起来看看 《删除》 这本书的介绍吧!
