题解 | #最大路径和#

有点抽象... 把问题转化为左上走到右下，走两次，所能获得的共同最大值。 统计的是两条路，每一步的点(x1,y1) 和 (x2,y2) 时的路径和，由于是同步移动的，满足x1+y1 = x2+y2，故可以省略y2.

每个路径都可以选择向右 或者 向下，那么每一步会衍生出4中情况，都要进递归。 如果边界，直接返回， 如果已经计算过，直接取缓存值， 如果抵达右下角，返回当前路径上的值， 如果当前两个点相遇，只取一份路劲上的值。

最后返回两个当前点的值及其所有延伸走向的值，是一个递归到深处再回来的模型。

import java.util.Arrays;
import java.util.Scanner;

//https://www.nowcoder.com/questionTerminal/8ecfe02124674e908b2aae65aad4efdf
public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        int N = scanner.nextInt();
        int [][] nums = new int [M][N];

//        for(int i=0;i<M;i++){
//            nums[i] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
//        }
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                nums[i][j] = scanner.nextInt();
            }
        }

        int ans = cherryPickUp(nums);
        System.out.println(ans);
        scanner.close();

    }

    private static int cherryPickUp(int[][] nums) {

        int M = nums.length,N = nums[0].length;
        int [][][] dp = new int [M][N][M];
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                for(int k=0;k<M;k++){
                    dp[i][j][k] = Integer.MIN_VALUE;
                }
            }
        }

        int ans = process(nums,0,0,0,dp);
        return ans < 0 ? 0 : ans;

    }

    private static int process(int[][] nums, int x1, int y1, int x2, int[][][] dp) {

        if(x1 == nums.length || y1 == nums[0].length || x2 == nums.length || x1 + y1 - x2 == nums[0].length){
            return Integer.MIN_VALUE;
        }

        //有缓存
        if(dp[x1][y1][x2] != Integer.MIN_VALUE){
            return dp[x1][y1][x2];
        }

        //到右下角了
        if(x1 == nums.length-1 && y1 == nums[0].length - 1 ){
            dp[x1][y1][x2] = nums[x1][y1];
            return dp[x1][y1][x2];
        }

        int next = Integer.MIN_VALUE;

        // 开始往四周走
        next = Math.max(next,process(nums,x1 + 1,y1,x2+1,dp));
        next = Math.max(next,process(nums,x1 + 1,y1,x2,dp));
        next = Math.max(next,process(nums,x1 ,y1 + 1,x2+1,dp));
        next = Math.max(next,process(nums,x1 ,y1 + 1,x2,dp));

        // 找不到
        if(nums[x1][y1] ==-1 || nums[x2][x1 + y1 - x2] == -1 || next == -1 ){
            dp[x1][y1][x2] = -1;
            return dp[x1][y1][x2];
        }

        if(x1 == x2){
            dp[x1][y1][x2] = nums[x1][y1] + next;
            return dp[x1][y1][x2];
        }

        dp[x1][y1][x2] = nums[x1][y1] + nums[x2][x1 + y1 - x2] + next;
        return dp[x1][y1][x2];
    }

}