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

2018-09-05 07:43:02来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题目:数字三角形

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

输入:第一行值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

下一篇:高精---大整数加法