C++数字三角形问题与dp算法
2019/7/10 22:33:17
本文主要是介绍C++数字三角形问题与dp算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:数字三角形
题目介绍:如图所示的数字三角形,要求从最上方顶点开始一步一步下到最底层,每一步必须下一层,求出所经过的数字的最大和。
输入:第一行值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 ]}
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #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算法,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的!
这篇关于C++数字三角形问题与dp算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2025-01-09CMS内容管理系统是什么?如何选择适合你的平台?
- 2025-01-08CCPM如何缩短项目周期并降低风险?
- 2025-01-08Omnivore 替代品 Readeck 安装与使用教程
- 2025-01-07Cursor 收费太贵?3分钟教你接入超低价 DeepSeek-V3,代码质量逼近 Claude 3.5
- 2025-01-06PingCAP 连续两年入选 Gartner 云数据库管理系统魔力象限“荣誉提及”
- 2025-01-05Easysearch 可搜索快照功能,看这篇就够了
- 2025-01-04BOT+EPC模式在基础设施项目中的应用与优势
- 2025-01-03用LangChain构建会检索和搜索的智能聊天机器人指南
- 2025-01-03图像文字理解,OCR、大模型还是多模态模型?PalliGema2在QLoRA技术上的微调与应用
- 2025-01-03混合搜索:用LanceDB实现语义和关键词结合的搜索技术(应用于实际项目)