DPwenti

blablabla

错误题解

最开始的写法，出错了，记录一下问题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=510;

int w[N][N],f[N][N];//w表示原路径值，f表示状态值。
int n;

int main(){
    cin >>n;
    for(int i=0;i<=n;i++)//这里i，j都要从1开始
        for(int j=0;j<=n;j++)
            cin>>w[i][j];//获取整个路径三角形
    for(int i=0;i<=n;i++){//这里i也要从1开始
        f[n][i]=w[n][i];//表示末尾的那行远路径值就是状态值。
    }
    for(int i=n-1;i;i--){//i>0可以简写
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);//<=>f[i][j]+=max(f[i+1][j],f[i+1][j+1])
        }
    }
    cout<<f[1][1]<<endl;
    return 0;
}

正确解法 $O(n^2)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=510;

int w[N][N],f[N][N];//w表示原路径值，f表示状态值。
int n;

int main(){
    cin >>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>w[i][j];//获取整个路径三角形
    for(int i=1;i<=n;i++){
        f[n][i]=w[n][i];//表示末尾的那行远路径值就是状态值。
    }
    for(int i=n-1;i;i--){//i>0可以简写
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);//<=>f[i][j]+=max(f[i+1][j],f[i+1][j+1])
        }
    }
    cout<<f[1][1]<<endl;
    return 0;
}

简化版本代码 $O(n^2)$

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510;
int n;
int f[N][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;i--){
        for(int j=1 ;j<=i;j++){
            f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
        }
    }
    cout << f[1][1] <<endl;
}