动态规划(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 | /**************************************************************** * Description: C++ implementation of Maximum path sum in a triangle. * Author: Alex Li * Date: 2023-06-14 19:51:06 * LastEditTime: 2023-06-14 20:51:32 ****************************************************************/ #include <iostream> using namespace std; const int MAXN=1005; int NT[MAXN][MAXN]; // use a array to store the Number Triangle. int N; // N is max level of the number triangles int MaxSum; // the final Maximum path sum. 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 | /**************************************************************** * Description: C++ implementation of Maximum path sum in a triangle. * Author: Alex Li * Date: 2023-06-14 19:51:06 * LastEditTime: 2023-06-14 22:32:27 ****************************************************************/ #include <iostream> using namespace std; const int MAXN=1005; int NT[MAXN][MAXN]; // use a array to store the Number Triangle. int Sum[MAXN][MAXN]; // store the max sum of path int N; // N is max level of the number triangles // from bottom to top int DFS(int x,int y){ if(Sum[x][y]==-1){ // if Sum[][] doesn't calculate. 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; for (int i = 1; i <=N; i++){ for (int j = 1; j <=i;j++){ cin>>NT[i][j]; } } for (int i = 1; i <=N; i++){ for (int j = 1; j <=i;j++){ Sum[i][j]=-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 | /**************************************************************** * Description: C++ implementation of Maximum path sum in a triangle. * Author: Alex Li * Date: 2023-06-14 19:51:06 * LastEditTime: 2023-06-14 22:38:23 ****************************************************************/ #include <iostream> using namespace std; const int MAXN=1005; int NT[MAXN][MAXN]; // use a array to store the Number Triangle. int Sum[MAXN][MAXN]; // store the max sum of path int N; // N is max level of the number triangles //from top to bottom int main(){ cin>>N; 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; } |
洛谷:P1216