方法1 记忆化搜索 dp递归写法

/**
 * f(i,j)=max(f(i+1,j),f(i+1,j+1));
 * 方法1  记忆化搜索
*/

import java.util.*;
public class Main{
    static int[][] f=new int[502][502];
    static int n;
    static int [][] arr;
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        arr=new int[n][n];
        for(int i=0;i<n;i++)
            for(int j=0;j<=i;j++)
                arr[i][j]=sc.nextInt();
        System.out.println(dp(0,0));
    }
    public static int dp(int i,int j){
        if(i==n-1) return arr[i][j];
        if(f[i][j]!=0) return f[i][j];
        f[i][j]=Math.max(dp(i+1,j),dp(i+1,j+1))+arr[i][j];
        return f[i][j];
    }
}

方法2：常规for循环dp

import java.util.*;
public class Main
{
    public static void main(String [] a){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int [][] f=new int[n+1][n+1];
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                f[i][j]=-0x3f3f3f3f;
            }
        }
        f[1][1]=sc.nextInt();
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                int t=sc.nextInt();
                f[i][j]=Math.max(f[i-1][j-1],f[i-1][j])+t;
            }
        }
        int res=0;
        for(int i=1;i<=n;i++){
            res=Math.max(f[n][i],res);
        }
        System.out.println(res);
    }
}