从最容易思考的记忆化搜索开始做起

方法1 记忆化搜索(有重复计算，因为我没有初始化dp数组，不过重复计算不多，能过，如果初始化 应该和for循环一样)，不对这个应该更快，因为没有遍历所有i1+j1=i2+j2的点(not sure)，而for循环是遍历所有。

/**
 * 定义f(i1,j1,i2,j2) 表示从(1,1)->(i1,j1,i2,j2)的路径和
 *
 * 为了方便假设两条线分别是l1，l2.
 * 
 * f(n,n,n,n) 为所求。分析f(n,n,n,n)他依赖于哪些状态：分别是l1从左或者上过来，l2从左或者上过来，组合
 * 起来一共有四种情况，而且l1,l2都是从邻居点过来的，也就是说，最终状态依赖的状态都满足i1+j1=i2+j2;同
 * 理其余状态依赖的状态也都满足这个。也就是说我们只需要遍历i1+j1=i2+j2的点就可以了。而i1+j1=i2+j2就是
 * 两条线同时走的情形。
 * 
 * 所以可以写出dp方程f(i1,j1,i2,j2)=max{(i1-1,j1,i2-1,j2),(i1,j1-1,i2,j2-1),(i1-1,j1,i2,j2-1),
                                       (i1,j1-1,i2-1,j2)}+(重合)?加一个元素：加两个元素。
 * 
 * 接下来用记忆化搜索即可
 * 
 * 数组定义为arr.
 * 
 * 初始状态是dp(1,1,1,1)=arr[1][1]//未用到 用记忆化搜索做了，没用遍历数组。
 *
 */
 import java.util.*;
 public class Main{
     static int [][] arr=new int[11][11];
     static int [][][][] f=new int[11][11][11][11];
     static int n;
     public static void main(String [] args){
         Scanner sc=new Scanner(System.in);
         n=sc.nextInt();
         while(true){
             int o1=sc.nextInt();
             int o2=sc.nextInt();
             int o3=sc.nextInt();
             if(o1==0&&o2==0&&o3==0) break;
             arr[o1][o2]=o3;
         }
         System.out.println(dp(n,n,n,n));
     }
     public static int dp(int i1,int j1,int i2,int j2){//只要进来一定i1+j1=i2+j2  因为最开始传入的是n n n n 
         if(i1==0||i2==0||j1==0||j2==0) return 0;//边界
         if(f[i1][j1][i2][j2]!=0) return f[i1][j1][i2][j2];
         f[i1][j1][i2][j2]=Math.max(Math.max(dp(i1,j1-1,i2-1,j2),Math.max(dp(i1-1,j1,i2-1,j2),dp(i1-1,j1,i2,j2-1))),dp(i1,j1-1,i2,j2-1));
         if(i1!=i2) f[i1][j1][i2][j2]+=arr[i1][j1];
         f[i1][j1][i2][j2]+=arr[i2][j2];
         return f[i1][j1][i2][j2];
     }
 }

方法2 三维dp

/**
 * 从方法1，我们知道其实f(n,n,n,n)状态只依赖于之前f(i1,j1,i2,j2)且i1+j1=i2+j2的状态。
 * 所以我们只需要遍历这些状态就可以了当然如果以后遇到两条线问题，直接记住结论同时走。
 * 要不然谁知道要规定个同时走。。。对吧。我是想破脑袋也不知道要规定同时走的。。
 * 不过从记忆化搜索倒推倒是可以得到同时走。
 * 
 * 又因为i1+j1=i2+j2  所以可以压缩一维 用k表示i1+i2；
 *  f(k,i1,i2) 来表示dp方程，含义：从(1,1,1,1)走到(i1,k-i1,i2,k-i2)的路径和最大值。
 *  f(k,i1,i2)=max{f(k-1,i1,i2),f(k-1,i1-1,i2),f(k-1,i1,i2-1),f(k-1,i1-1,i2-1)}+
 *             重合?加一个元素：加两个元素。
 *  k从2开始，因为i1+j1最小值就是2.
 * 
*/
import java.util.*;
public class Main{
    public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int [][] arr=new int[n+1][n+1];
        int[][][] f=new int[n+n+1][n+1][n+1];
        while(true){
            int o1=sc.nextInt();
            int o2=sc.nextInt();
            int o3=sc.nextInt();
            if(o1==0||o2==0) break;
            arr[o1][o2]=o3;
        }
        for(int k=2;k<=2*n;k++){
                for(int i1=1;i1<=n;i1++){
                    for(int i2=1;i2<=n;i2++){
                        int j1=k-i1;
                        int j2=k-i2;
                        if(j1>=1&&j2>=1&&j1<=n&&j2<=n){//保证坐标的合法
                            f[k][i1][i2]=Math.max(f[k-1][i1-1][i2-1],Math.max(f[k-1][i1][i2-1],Math.max(f[k-1][i1][i2],f[k-1][i1-1][i2])));
                            if(i1!=i2) f[k][i1][i2]+=arr[i1][k-i1];
                            f[k][i1][i2]+=arr[i2][k-i2];
                        }
                    }
                }
        }
        System.out.println(f[2*n][n][n]);
    }
}