线性动态规划-数字金字塔
洛谷：P1216 OJ平台：T1258
动态规划(Dynamic Programming, DP)是对一类最优化问题的解决方法。
数字金字塔：观察下面的数字多字塔，写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大，每一步可以从当前点走到左下方的点，也可以到达右下方的点。
方法1：遍历搜索(暴力)
此方法就是把所有可能性都搜索，然后比较大小。算法复杂度O(2N)
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 |
/**************************************************************** * 代码作者: Alex Li * 创建时间: 2023-06-14 19:51:06 * 最后修改: 2024-12-23 22:55:47 * 文件描述: 求数字三角形最大路径和的C++实现，使用递归方法（深度优先搜索） ****************************************************************/ #include <iostream> using namespace std; const int MAXN = 1005; // 定义最大三角形层数 int NT[MAXN][MAXN]; // 用于存储数字三角形的二维数组 int N; // 三角形的层数 int MaxSum; // 存储最终的最大路径和 // 深度优先搜索函数 void DFS(int x, int y, int Current) { // 如果已经到达三角形的最后一层 if (x == N) { if (Current > MaxSum) // 更新最大路径和 MaxSum = Current; return; } // 递归搜索当前节点的两个子节点 DFS(x + 1, y, Current + NT[x + 1][y]); // 左子节点 DFS(x + 1, y + 1, Current + NT[x + 1][y + 1]); // 右子节点 } int main() { cin >> N; // 输入三角形的层数 for (int i = 1; i <= N; i++) { for (int j = 1; j <= i; j++) { cin >> NT[i][j]; // 输入每个位置的数字 } } MaxSum = 0; // 初始化最大路径和 DFS(1, 1, NT[1][1]); // 从顶点开始深度优先搜索 cout << MaxSum << endl; // 输出最大路径和 return 0; } |
方法2：记忆搜索。
建立新的数组]Sum[][]，记录从底向上每一层的最优路径。时间复杂度O(n^2)
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 44 45 46 47 48 49 50 51 |
/**************************************************************** * 代码作者: Alex Li * 创建时间: 2023-06-14 21:45:53 * 最后修改: 2024-12-24 05:42:10 * 文件描述: 数字三角形最大路径和，使用从底向上的记忆化搜索方法 ****************************************************************/ #include <iostream> #include <vector> using namespace std; vector<vector<int>> NT; // 存储数字三角形的二维数组 vector<vector<int>> Sum; // 存储到每个位置的最大路径和，-1 表示未计算 int N; // 数字三角形的层数 // 从底向上计算路径最大和的递归函数 int DFS(int x, int y) { // 如果当前位置的最大路径和尚未计算 if (Sum[x][y] == -1) { // 如果当前是最后一层，最大路径和就是该点的值 if (x == N) Sum[x][y] = NT[x][y]; else // 否则递归计算左右子节点的最大路径和，并取较大值加上当前点值 Sum[x][y] = NT[x][y] + max(DFS(x + 1, y), DFS(x + 1, y + 1)); } return Sum[x][y]; // 返回当前位置的最大路径和 } int main() { cin >> N; // 输入三角形的层数 // 初始化数字三角形和动态规划存储数组 NT.resize(N + 1, vector<int>(N + 1)); Sum.resize(N + 1, vector<int>(N + 1, -1)); // 初始化为 -1 表示未计算 // 输入数字三角形 for (int i = 1; i <= N; i++) { for (int j = 1; j <= i; j++) { cin >> NT[i][j]; } } // 从顶点 (1, 1) 开始计算最大路径和 DFS(1, 1); // 输出从顶点到底部的最大路径和 cout << Sum[1][1] << endl; return 0; } |
方法3： 动态规划
用Sum[][]数组记录从上到下，每一步的最优解。O(n^2)
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 44 45 46 | /**************************************************************** * 代码作者: Alex Li * 创建时间: 2023-06-14 22:35:29 * 最后修改: 2024-12-24 09:00:09 * 文件描述: 数字三角形最大和，动态规划方法 O(N^2) ****************************************************************/ #include <iostream> #include <vector> using namespace std; int main() { int N; // 三角形的层数 cin >> N; // 使用 vector 初始化数字三角形和路径和数组 vector<vector<int>> NT(N + 1, vector<int>(N + 1, 0)); // 数字三角形 vector<vector<int>> Sum(N + 1, vector<int>(N + 1, 0)); // 路径和数组 // 输入数字三角形 for (int i = 1; i <= N; i++) { for (int j = 1; j <= i; j++) { cin >> NT[i][j]; // 输入每个位置的数字 } } // 初始化顶点的路径和 Sum[1][1] = NT[1][1]; // 从第二层开始，计算从顶点到每个位置的最大路径和 for (int i = 2; i <= N; i++) { for (int j = 1; j <= i; j++) { // 每个位置的路径和为其父节点的最大路径和加上当前节点的值 Sum[i][j] = max(Sum[i - 1][j - 1], Sum[i - 1][j]) + NT[i][j]; } } int ans = 0; // 存储最终的最大路径和 // 遍历最后一层，找出从顶点到底部的最大路径和 for (int j = 1; j <= N; j++) { ans = max(ans, Sum[N][j]); } cout << ans << endl; // 输出最大路径和 return 0; } |
如果打印最大和的路径，需要加一段代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | // 遍历最后一层，找出从顶点到底部的最大路径和 int maxS=0; for (int j = 1; j <= N; j++) { if(Sum[N][j]>ans){ ans=Sum[N][j]; maxS=j; } } cout<<NT[N][maxS]<<' '; for(int i=N-1;i>=2;i--){ if(Sum[i][maxS-1]>Sum[i][maxS]){ cout<<NT[i][maxS-1]<<' '; maxS--; } else{ cout<<NT[i][maxS]<<' '; } } cout<<Sum[1][1]<<' '; |