算法

这个题目和leetcode上面的摘樱桃是一样的思路和做法。
比较麻烦的感觉就是下标处理了。
就是把来回分成两条路，保证两条路不相交。

Java 代码

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(), n = in.nextInt();
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = in.nextInt();
            }
        }
        in.close();
        System.out.println(maxValue(matrix));
    }

    private static int maxValue(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][][] dp = new int[m + n - 1][m][m];
        for (int i = 1; i < m + n - 1; ++i) {
            for (int j = Math.max(i - n + 1, 0); j <= Math.min(m - 1, i); ++j) {
                int k = (i == m + n - 2) ? j : j + 1;
                for (; k <= Math.min(m - 1, i); ++k) {
                    int c1 = i - j, c2 = i - k;
                    int cur = matrix[j][c1] + matrix[k][c2];
                    if (i > j && i > k) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j][k] + cur);
                    }
                    if (j > 0 && i > k) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - 1][k] + cur);
                    }
                    if (k > 0 && i > j) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j][k - 1] + cur);
                    }
                    if (j > 0 && k > 0) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - 1][k - 1] + cur);
                    }
                }
            }
        }
        return dp[m + n - 2][m - 1][m - 1];
    }
}