优化做法（O^3）

/*
 * @Author: YMYS
 * @Date: 2024-12-17 10:42:49
 * @LastEditTime: 2024-12-17 22:58:30
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法提高课\1.动态规划\1.数字三角形模型\3.方格取数.cpp
 * @URL:https://www.acwing.com/problem/content/1029/
 * @Description: 1027. 方格取数
 */
#include<bits/stdc++.h>

using namespace std;

const int N = 20;

int t;
int x,y,v;
int f[N][N];//单点的值
int dp[2*N][N][N];//dp数组值

int main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    // cin>>T;
    // while(T--){
    //     solve();
    // }

    cin>>t;
    while (cin>>x>>y>>v, x||y||v) f[x][y] = v;

    for(int k=1;k<=2*t;k++){
        for(int i1=1;i1<=t;i1++){
            for(int i2=1;i2<=t;i2++){
                int y1 = k-i1, y2 = k-i2;

                if(y1>=1 && y1 <= t && y2>=1 && y2<=t){

                    //赋值给xx基础的f[][]值
                    int xx = f[i1][y1];
                    if(i1 != i2) xx += f[i2][y2];

                    //引用，等价替换
                    //【如果不加&, 那就是只是tmp的值在变化】
                    //【加了&后，就是在给dp[k][i1][i2]赋值】
                    int &tmp = dp[k][i1][i2];

                    tmp = max(tmp, dp[k-1][i1-1][i2-1] + xx);//这里的dp[][][]数组等价于dp[i1-1][y1][i2-1][y2]
                    tmp = max(tmp, dp[k-1][i1][i2-1] + xx);//dp[i1][y1-1][i2-1][y2]
                    tmp = max(tmp, dp[k-1][i1-1][i2] + xx);//dp[i1-1][y1][i2][y2-1]
                    tmp = max(tmp, dp[k-1][i1][i2] + xx);//dp[i1][y1-1][i2][y2-1]
                }
            }
        }
    }

// cout<<"xxxx"<<endl;
    cout<<dp[2*t][t][t]<<endl;

    return 0;
}

暴力做法（O^4）

/*
 * @Author: YMYS
 * @Date: 2024-12-17 10:42:49
 * @LastEditTime: 2024-12-17 22:58:30
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法提高课\1.动态规划\1.数字三角形模型\3.方格取数.cpp
 * @URL:https://www.acwing.com/problem/content/1029/
 * @Description: 1027. 方格取数
 */
#include<bits/stdc++.h>

using namespace std;

const int N = 20;
/*
 * 暴力做法，直接四层循环遍历
 * 整体遍历思想和优化后版本一样
 */
int t;
int x,y,v;
int f[N][N];
int dp[N][N][N][N];

int main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    // cin>>T;
    // while(T--){
    //     solve();
    // }

    cin>>t;
    while (cin>>x>>y>>v, x||y||v) f[x][y] = v;

    for(int i=1;i<=t;i++){
            for(int j=1;j<=t;j++){
                for(int m=1;m<=t;m++){
                    for(int n=1;n<=t;n++){
                        dp[i][j][m][n]
                        =
                        max(
                            max(dp[i-1][j][m-1][n], dp[i-1][j][m][n-1]),
                            max(dp[i][j-1][m-1][n], dp[i][j-1][m][n-1])
                        ) 
                        + f[i][j] + f[m][n];

                        if(i==m && j==n) dp[i][j][m][n] -= f[i][j];
                    }
                }
            }
        }

// cout<<"xxxx"<<endl;
    cout<<dp[t][t][t][t]<<endl;

    return 0;
}