深搜→记忆化搜索→递推（二维DP）→一维DP

解题思路:

首先要知道最后的结果在最后一行中间产生，为什么？左右移的差不会超过1

向左走多少就会尽可能向右走多少。

若N为奇数，肯定落在n/2+1的位置

若N为偶数，则结果应该是max(n/2,n/2+1)

第一步：画搜索树

第二步：暴力DFS

我们可以根据N的奇偶确定递归的终点，

若n为奇，则终点就是（n,n/2+1)，即（5，3）对应2这个数字

若为偶，则终点为max((n,n/2),(n,n/2+1)) 以n为4为例，则对应7或4

递归公式：dfs(x,y)=max(dfs(x-1，y),dfs(x-1,y-1))+arr[x][y]

递归边界：x<1||y<1,dfs(x,y)=0

参考代码：

import java.io.*;
import java.util.*;
 
public class Main {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    static long [][]arr;
    public static void main(String[] args) throws IOException {
            int n=Integer.parseInt(br.readLine());
            arr=new long[n+2][n+2];
            String []s;
            for(int i=1;i<=n;i++){
                s=br.readLine().split(" ");
                for(int j=1;j<=i;j++){
                    arr[i][j]=Long.parseLong(s[j-1]);
                }
            }
            long result=0;
            if(n%2!=0){
                result=dfs(n,n/2+1);
            }else{
                result=dfs(n,n/2)>dfs(n,n/2+1)?dfs(n,n/2):dfs(n,n/2+1);
            }
            pw.println(result);
            pw.flush();
         
    }
    private static long dfs(int x,int y){
        if(x<1||y<1){
            return 0;
        }
         
        return Math.max(dfs(x-1,y-1),dfs(x-1,y))+arr[x][y];

运行结果：时间超限:   55 分

第三步：记忆化搜索

考虑到搜索树里，蓝色框中的dfs(x,y)在左支中已经计算过，无需重复递归，记录左支的结果

参考代码：

import java.io.*;
import java.util.*;
 
public class Main {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    static long [][]arr;
    static long [][]map;
    public static void main(String[] args) throws IOException {
            int n=Integer.parseInt(br.readLine());
            arr=new long[n+2][n+2];
            map=new long[n+1][n+1];
            String []s;
            for(int i=1;i<=n;i++){
                s=br.readLine().split(" ");
                for(int j=1;j<=i;j++){
                    arr[i][j]=Long.parseLong(s[j-1]);
                }
            }
            long result=0;
            if(n%2!=0){
                result=dfs(n,n/2+1);
            }else{
                result=dfs(n,n/2)>dfs(n,n/2+1)?dfs(n,n/2):dfs(n,n/2+1);
            }
            pw.println(result);
            pw.flush();
         
    }
    private static long dfs(int x,int y){
        if(map[x][y]!=0){
            return map[x][y];
        }
        long sum=0;
        if(x<1||y<1){
            sum= 0;
        }else{
            sum=Math.max(dfs(x-1,y-1),dfs(x-1,y))+arr[x][y];
        }
        map[x][y]=sum;
        return sum;
    }
}

运行结果：时间超限:   64 分

没关系，继续优化

第四步：递推

递推公式：dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+arr[i][j]

参考代码：
import java.io.*;
import java.util.*;
 
public class Main {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    static long [][]arr;
    static long [][]dp;
    public static void main(String[] args) throws IOException {
            int n=Integer.parseInt(br.readLine());
            arr=new long[n+2][n+2];
            dp=new long[n+1][n+1];
            String []s;
            for(int i=1;i<=n;i++){
                s=br.readLine().split(" ");
                for(int j=1;j<=i;j++){
                    arr[i][j]=Long.parseLong(s[j-1]);
                }
            }
           for(int i=1;i<=n;i++){
               for(int j=1;j<=i;j++){
                  dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1])+arr[i][j]; 
               }
           }
           if(n%2!=0){
            pw.println(dp[n][n/2+1]);
           }else{
               pw.println(dp[n][n/2]>dp[n][n/2+1]?dp[n][n/2]:dp[n][n/2+1]);
           }
            pw.flush();
         
    }
}

运行结果：100分 运行时间: 490ms    消耗内存: 15616KB

继续优化,二维dp→一维dp

因为dp[i][j]肯定是从i-1转换来的,所以不需要管行变化

dp[j]=max(dp[j],dp[j-1])+arr[i][j]

参考代码：

import java.io.*;
import java.util.*;
 
public class Main {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    static long [][]arr;
    static long []dp;
    public static void main(String[] args) throws IOException {
            int n=Integer.parseInt(br.readLine());
            arr=new long[n+2][n+2];
            dp=new long[n+1];
            String []s;
            for(int i=1;i<=n;i++){
                s=br.readLine().split(" ");
                for(int j=1;j<=i;j++){
                    arr[i][j]=Long.parseLong(s[j-1]);
                }
            }
           for(int i=1;i<=n;i++){
               for(int j=i;j>=1;j--){
                  dp[j]=Math.max(dp[j],dp[j-1])+arr[i][j]; 
               }
           }
           if(n%2!=0){
            pw.println(dp[n/2+1]);
           }else{
               pw.println(dp[n/2]>dp[n/2+1]?dp[n/2]:dp[n/2+1]);
           }
            pw.flush();
         
    }
}

运行结果：100分 运行时间: 583ms    消耗内存: 15504KB

注意事项:

j应该倒着遍历，即从每一行的最后一个数字向前遍历

为什么？如果正着遍历，那么dp[j]会记录这次的结果作为j+1的dp[j-1]

例如i=2时，

j=1时，dp[1]=dp[1]+arr[2][1]=10

j=2时，dp[2]=dp[1]+arr[2][2]=10+8=18

但是其实dp[2]应该等于7+8=15

所以j不应该从1开始，而是从j=i开始向前遍历

参考代码: