时间:2021-05-20
题目:数字三角形
题目介绍:如图所示的数字三角形,要求从最上方顶点开始一步一步下到最底层,每一步必须下一层,求出所经过的数字的最大和。
输入:第一行值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.
总结
以上所述是小编给大家介绍的C++数字三角形问题与dp算法,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
题目描述:输入三角形的三条边长,判断是否能构成一个三角形(不考虑退化三角形,即面积为零的三角形),是什么样的三角形(直角、锐角、钝角、等边、等腰)。函数声明为:
本文主要研究的是输入三角形边长判断其类型并输出面积,用C语言实现,具体如下。思路:首先判断所给的三条边是否能够组成三角形,若可以组成三角形,则判断该三角形是什么
问题描述杨辉三角形又称Pascal三角形,它的第i+1行是(a+b)^n的展开式的系数。它的一个重要性质是:三角形中的每个数字等于它两肩上的数字相加。下面给出了
我先说如何制作三角形吧,相信大家在平时逛网站的时候都会看到一些导航栏中的三角形吧,比如说:网易首页的头部菜单栏中,也会有这样的三角形当鼠标经过时,三角形会垂直翻
我先说如何制作三角形吧,相信大家在平时逛网站的时候都会看到一些导航栏中的三角形吧,比如说:网易首页的头部菜单栏中,也会有这样的三角形当鼠标经过时,三角形会垂直翻