C++数字三角形问题与dp算法
2018-09-05 07:43:02来源:博客园 阅读 ()
题目:数字三角形
题目介绍:如图所示的数字三角形,要求从最上方顶点开始一步一步下到最底层,每一步必须下一层,求出所经过的数字的最大和。
输入:第一行值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 #include <iostream> 2 using namespace std; 3 int main() 4 { 5 int i; 6 int n; 7 cin >> n; 8 int **p = new int *[n]; 9 for (i = 0; i < n; i++) 10 { 11 p[i] = new int[n]; 12 } 13 for (i = 0; i < n; i++) 14 { 15 for (int j = 0; j <= i; j++) 16 { 17 cin >> p[i][j]; 18 } 19 } 20 for (i = 1; i < n; i++) 21 { 22 p[i][0] += p[i - 1][0]; 23 } 24 for (i = 1; i < n; i++) 25 { 26 p[i][i] += p[i - 1][i - 1]; 27 } 28 for (i = 2; i < n; i++) 29 { 30 for (int j = 1; j < i; j++) 31 { 32 p[i][j] += (p[i - 1][j - 1] > p[i - 1][j]) ? p[i - 1][j - 1] : p[i - 1][j]; 33 } 34 } 35 for (i = 0; i < n; i++) 36 { 37 for (int j = 0; j <= i; j++) 38 { 39 cout << p[i][j] << " "; 40 } 41 cout << endl; 42 } 43 }
结果如下图:
所以最下层的数字和最大值是24.
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:你不知道的c++11
下一篇:高精---大整数加法
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash