动态规划:数字金字塔 <--- 最后一步法
【问题描述】 观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。
在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。 【样例输入】 第一个行包含R(1≤ R≤1000),表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。 【样例输出】 单独的一行,包含那个可能得到的最大的和。 【动态规划问题分析思路】 此问题是“最值型”问题,适用于利用动态规划方法解决。 步骤如下: 1.确定状态 ■ 研究最优策略的最后一步 ■ 化为子问题 ■ 注意:状态在动态规划中的作用属于定海神针 2.状态转移方程 ■ 根据子问题定义直接得到 3.初始条件和边界情况 ■ 细心,考虑周全 ■ 注意:不能通过状态转移方程计算出的值设为初始条件 4.计算顺序 ■ 原则是利用之前的计算结果。故可依据状态转移方程确定计算顺序。 上述分析思路详见:https://www.bilibili.com/video/BV1xb411e7ww 【本题利用最后一步法的解题思路】
将金字塔拉伸为如图所示形状,更便于分析。 最后一步:从最高点到底部任意处(i,j)时,路径所经过的数字和最大。 子问题:从最高点到(i-1,j-1)处所经过的数字和最大值,及从最高点到(i-1,j)处所经过的数字和最大值的较大值加上(i,j)处结点的值。 状态:设f[i][j]表示从最高点到(i,j)路径所经过的数字和的最大值。 状态转移方程:f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]; -->a[i][j]表示结点(i,j)的值,即图中圆圈中的值。 初始条件:f[1][1]=a[1][1]; -->因为此分析过程将二维数组的两个维度的下标都从1开始,所以f[1][1]不能通过上面确定的状态转移方程计算出来,所以必须明确指定。 计算顺序:自动依据状态转移方程确定。 【算法代码】
#include <bits/stdc++.h> using namespace std; const int maxn=1005; const int inf=0x3f3f3f3f; int a[maxn][maxn]; int f[maxn][maxn]; int ans=-inf; int main() { int n; cin>>n; for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { cin>>a[i][j]; } } for(int i=1; i<=n; i++) { for(int j=0; j<=i+1; j++) { f[i][j]=-inf; //若输入有负数,此段代码就能避坑 } } f[1][1]=a[1][1]; for(int i=2; i<=n; i++) { for(int j=1; j<=i; j++) { f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]; } } for(int i=1; i<=n; i++) { ans=max(ans,f[n][i]); } cout<<ans<<endl; return 0; } /* in: 5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11 out: 86 ----------------------------- in: 5 3 2 6 1 8 7 9 1 3 6 2 5 3 2 1 out: 24 ----------------------------- in: 10 -6 -4 -5 -3 7 5 3 7 -2 1 10 2 -6 2 -6 -8 3 8 6 7 9 -4 -10 0 -3 4 9 2 0 5 5 5 10 -6 -5 -4 -9 7 4 9 8 -5 -2 3 2 -7 -4 0 -10 -8 -4 3 -5 8 9 out: 25 */
上述代码是从上往下分析得出的结果。若从下往上分析,则代码为:
#include<bits/stdc++.h> using namespace std; const int maxn=505; int a[maxn][maxn]; int f[maxn][maxn]; int n; int main() { cin>>n; for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { cin>>a[i][j]; } } for(int i=n; i>=1; i--) { for(int j=i; j>=1; j--) { f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j]; } } cout<<f[1][1]<<endl; } /* in: 10 -6 -4 -5 -3 7 5 3 7 -2 1 10 2 -6 2 -6 -8 3 8 6 7 9 -4 -10 0 -3 4 9 2 0 5 5 5 10 -6 -5 -4 -9 7 4 9 8 -5 -2 3 2 -7 -4 0 -10 -8 -4 3 -5 8 9 out: 25 */
【参考文献】 https://www.bilibili.com/video/BV1xb411e7ww https://blog..net/m0_47642376/article/details/111053049 https://www.acwing.com/solution/content/3485/