内容简介:题目:数字三角形题目介绍:如图所示的数字三角形,要求从最上方顶点开始一步一步下到最底层,每一步必须下一层,求出所经过的数字的最大和。
题目:数字三角形
题目介绍:如图所示的数字三角形,要求从最上方顶点开始一步一步下到最底层,每一步必须下一层,求出所经过的数字的最大和。
输入:第一行值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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 蓝桥杯 ADV-135 算法提高 三角形面积
- 判断点是否在三角形内的算法精度问题
- CSS三角形和饼图
- go gl 彩色的三角形
- 【Leetcode】120.三角形最小路径和
- 【WPF】用三角形网格构建三维图形
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Spring揭秘
王福强 / 人民邮电出版社 / 2009.8 / 99.00元
没有教程似的训导,更多的是说故事般的娓娓道来,本书是作者在多年的工作中积累的第一手Spring框架使用经验的总结,深入剖析了Spring框架各个模块的功能、出现的背景、设计理念和设计原理,揭开了Spring框架的神秘面纱,使你“知其然,更知其所以然”。每部分的扩展篇帮助读者活学活用Spring框架的方方面面,同时可以触类旁通,衍生出新的思路和解决方案。 本书内容全面,论述深刻入理,必将成为每......一起来看看 《Spring揭秘》 这本书的介绍吧!
RGB CMYK 转换工具
RGB CMYK 互转工具
HEX CMYK 转换工具
HEX CMYK 互转工具