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 #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.