C++数字三角形问题与DP算法

栏目: C++ · 发布时间: 6年前

内容简介:题目:数字三角形题目介绍:如图所示的数字三角形,要求从最上方顶点开始一步一步下到最底层,每一步必须下一层,求出所经过的数字的最大和。

题目:数字三角形

题目介绍:如图所示的数字三角形,要求从最上方顶点开始一步一步下到最底层,每一步必须下一层,求出所经过的数字的最大和。

C++数字三角形问题与DP算法

输入:第一行值n,代表n行数值;后面的n行数据代表每一行的数字。

输出:经过数字的最大和。

例:

输入:

4

1

3 2

4 10 1

4 3 2 20

输出:

24

分析:这也是一个典型的贪心算法无法解决的问题,同样可以用动态规划(dp算法)来解决。把边界数字首先初始化到结果矩阵中,再根据状态方程完成结果矩阵的遍历。需要注意的就是数组不是矩形而是三角形,与传统的状态方程相比需要做点改进。

数组编号:

C++数字三角形问题与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;

}

}

结果如下图:

C++数字三角形问题与DP算法

所以最下层的数字和最大值是24.

Linux公社的RSS地址: https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址: https://www.linuxidc.com/Linux/2018-09/153946.htm


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

新零售:低价高效的数据赋能之路

新零售:低价高效的数据赋能之路

刘润 / 中信出版集团 / 2018-9 / 65.00元

小米新零售,如何做到20倍坪效? 天猫小店,如何利用大数据助力线下零售? 盒马鲜生,为什么坚持必须用App才能买单? 名创优品,实体小店在电商冲击下,如何拥抱春天? 新零售的未来在何方?什么样的思维模式才可应对? 新零售,不是商界大佬的专用名词,它就在我们生活触手可及的各个角落——小到便利店的酸奶,大到京东商城的冰箱,都蕴含着消费者、货物、经营场所三者共同作用的经济逻......一起来看看 《新零售:低价高效的数据赋能之路》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

MD5 加密
MD5 加密

MD5 加密工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具