数字三角形
题目 数字三角形
思路分析
求一条路径 累加最大值
首先完全可以用dfs做 得到所有方案 再遍历取得最大的答案
又可以从dp的角度思考——省去递 直接推
把某点之前的点当已知答案 用已知的答案推出当前点
所以为了方便表示状态 我们给每个点进行编号
就可以用f[i][j]表示 所有从起点 走到i，j这个点的所有走法 的距离最大值
我们发现每个点 不过就是两种情况得到
我们这个f[3,2]（起点到3,2的距离最大值 要么是从起点到2,1的最大值中加上这个当前点1 要么是从起点到2,2的最大值 加上这个点1）
所以也就是说 当前点的状态 要么就从左上角的转移过来 要么从右上角的转移过来
可以画出dp分析图
再考虑特殊情况 因为是从左上右上转移过来 不可避免的就会碰到左上或者右上没有值的情况（三角形的边缘）
此时就得置成-inf吧 才能保证答案是从有值的那一边转移过来
那么就得初始化成这样
那么最后的答案应该就在最下面这一层
f[n][1-m] 还得从这里面遍历找到一个最大的作为真正答案
（为什么？考虑实际含义 f[n][1]表示到n,1的所有路径长的最大值 f[n][2]表示到n，2的…… 只是针对一个点来说的 那为什么背包问题可以直接取nm——从这个写法出发其实他也得这样做 只不过加了一点额外考虑 从前n个物品里选5个 自然会比在前n个物品里选3个得到的价值更大吧 所以直接在nm里取答案）
发现还不如就干脆从下面开始做起 推到上面去
这样答案就在1,1的地方了 不需要遍历一整行 甚至连边界情况也不需要考虑了
因为都是从左下和右下转移过来的
那么这时状态转移方程就变成了
f[i,j]=max(f[i+1][j]+a[i][j],f[i+1][j+1]+a[i][j]);
(另外提一句 背包问题一开始也是这样分析的 只不过它那种选与不选用这种图形很难描述出来 我们这里也不过只是借助图像了解坐标 实际上就可以把图形省略掉 直接从集合的角度来去思考这个状态转移问题 y总的dp分析法确实nb）
解决完这道题后 拓展一个内容
每走到一个点 就选它下一个能选的最大的点行不行（可能因为这里是找最大 如果找最小 没负权的话应该是可行的）
其实这个问题 把树拓展到图
就是我们的最短路问题中迪杰斯特拉算法和spfa算法的比较问题了
当时就提到了 迪杰斯特拉基于贪心 而spfa基于动态规划
现在应该更理解了这个问题吧
spfa其实就是这个问题的一个拓展吧 这里每个点只能从两个孩子得到 而图中 就不像二叉树一样只能从两边得到了 在图中 加入该点后 看总长度是否变化 每步都基于全局考虑 而非逐步最优的贪心
代码实现
从上往下推
#include<bits/stdc++.h>
using namespace std;
const int N=510,INF=1e9;
int a[N][N];
int f[N][N];
int n;
int main()
{
cin>>n;
//下标从1开始 因为有i-1操作 防止0-1越界
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
//从0开始 因为要在外围多加一层-inf
for(int i=0;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]+a[i][j],f[i-1][j]+a[i][j]);
// 左上 右上
}
}
int res=-INF;
//从到各点的权重中找一个最大的
for(int i=1;i<=n;i++)
res=max(res,f[n][i]);
cout<<res;
return 0;
}
从下往上推
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int f[N][N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>f[i][j];
//直接从下往上推 最底下那层不用管 倒数第二层推上去
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
f[i][j]=max(f[i+1][j+1],f[i+1][j])+f[i][j];
// 右下 左下
}
}
//顶部就是答案
cout<<f[1][1];
return 0;
}
💬 评论