#include<bits/stdc++.h>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int f[N][N];
int a[N][N];
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++){ //因为有负数，所以应该将两边也设为-INF
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]=a[i][j]+max(f[i-1][j-1],f[i-1][j]);
}
}
int res=-INF;
for(int i=1;i<=n;i++) res=max(res,f[n][i]);
cout<<res<<endl;
}
也可以倒序dp，更简单些，因为倒序不需要考虑边界问题
#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;i>=1;i--){
for(int j=i;j>=1;j--){
f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j];
}
}
cout<<f[1][1]<<endl;
}
倒序dp并没有必要将第二个循环倒序
第二个正序倒序一样的啊，不影响结果
所以没有必要
正确的，直接从倒数第二行开始就行
统一性吧，毕竟一样的格式容易记忆，没有什么必要不必要的
大佬很好的思路！
爆赞
不用考虑边界可太香了，Orz
memset(f,-0x3f,sizeof f);
用memset也能过
纯萌新 只想弱弱的问一句这个能用trie写吗 我看到这个第一个想到的就是trie
说一说思路呗
感谢
牛！
把所有的f都设置为-INF为什么不可以呀
都设置为-INF也可以啊
为什么 -INF 变成 -INT_MAX 就过不了了
这个跟负权图论有什么区别
orz!
baozan
Orz
为什么倒序dp就不用考虑边界了呢
我的个人理解是，如果是倒序的话，方向是从右向左，从上到下，首先i = n的时候， 最后一排会出现f[i][j] = a[i][j]的情况，然后处理倒数第二行时，他是max(f[i+1][j],f[i+1][j+1])对比的下方和右下方，即使是最右边的元素也不会处理到边界问题，所以可以不对f初始化为-INF，但是如果正序dp的话，他选择的方式是max(f[i-1][j-1],f[i-1][j])，是左上角和上方，这样的话最左边的元素会处理到边界，所以需要处理边界问题。。个人愚见，多多海涵！
正序的话，当前节点如果在右边界，则没有右边下来的父节点。倒过来看 每个节点一定会有两个子节点
您好，我有点不理解，倒序dp时，求每个点的最大值为什么是f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j];，而不是f[i][j]=max(f[i+1][j]+f[i][j],f[i+1][j+1])+f[i][j];,即为什么左子节点不加上该点的值呢？？
f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j]楼主的这个式子是在max结束后才加上f[i][j]， 相当于取最大值再加上该点的值
也可以换成f[i][j]=max(f[i+1][j]+f[i][j],f[i+1][j+1+f[i][j]])，这就是先用左右子节点加上自身再判断大小。
嗷嗷嗷！谢谢啦，是我看花了
i从n开始，那i+1不是超了吗，
貌似会将没有赋值的数组元素初始化0，我dev编译器是这样的
int res=-INF;
for(int i=1;i<=n;i++) res=max(res,f[n][i]);
这个是什么意思
res初始化为负无穷，遍历最后一行，找出最大值即为答案。
个人理解:正序dp将所有的路径都走了一遍，所有路径所求出来的值都在最后一行，需要遍历最后一行找出所有路径的值的最大值
好方法