基于动态规划的N*N矩阵最大路径和（含最大值重复计算）求解

给定NN的矩阵mat[][]，需找出从左上角(0,0)到右下角(N–1,N–1)的路径，要求路径元素总和最大，且需额外加上路径中的最大值（即最大值被计算两次）。仅允许从单元格(i,j)向下移动到(i+1,j)或向右移动到(i,j+1)。要求使用两个大小为NN的数组实现动态规划，时间复杂度为O(N²)。

原代码说明 #

你提供的代码采用DFS枚举所有路径的方式实现，时间复杂度为O(2^(2N))，远高于O(N²)，对于较大的N会严重超时。该代码在测试用例[[1,2,3],[4,5,6],[7,8,9]]中返回38，对应路径1->4->7->8->9，最大值9被重复计算一次。

原代码如下：

import java.util.ArrayList;
import java.util.List;

public class MatrixPaths {

    public static List<List<Integer>> generatePaths(int[][] matrix) {
        List<List<Integer>> allPaths = new ArrayList<>();
        dfs(0, 0, matrix, new ArrayList<>(), allPaths);
        return allPaths;
    }

    private static void dfs(int i, int j, int[][] matrix, List<Integer> currentPath, List<List<Integer>> allPaths) {
        int n = matrix.length;

        // Add the current cell to the current path
        currentPath.add(matrix[i][j]);

        // Check if we have reached the bottom-right cell
        if (i == n - 1 && j == n - 1) {
            allPaths.add(new ArrayList<>(currentPath));
        } else {
            // Move down
            if (i + 1 < n) {
                dfs(i + 1, j, matrix, currentPath, allPaths);
            }

            // Move right
            if (j + 1 < n) {
                dfs(i, j + 1, matrix, currentPath, allPaths);
            }
        }

        // Remove the last element to backtrack
        currentPath.remove(currentPath.size() - 1);
    }
    
    public static int maxSV(int A[][]) {
        List<List<Integer>> allPaths = generatePaths(A);
        int maxSum = 0;
        for (List<Integer> path : allPaths) {
            int sum = 0;
            int maxElement = Integer.MIN_VALUE; // Initialize maxElement to the smallest possible value
            for (int element : path) {
                sum += element;

                // Update maxElement if the current element is greater
                maxElement = Math.max(maxElement, element);
            }
            sum += maxElement;
            // Update maxSum if the current sum is greater
            maxSum = Math.max(maxSum, sum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        System.out.println(maxSV(matrix));
    }
}

动态规划解法（O(N²)时间复杂度） #

思路 #

我们维护两个N*N的数组：

• s[][]：记录到达每个位置(i,j)时，路径的总和 - 最大值的最大值
• m[][]：记录对应s[i][j]路径中的最大值

最终结果为s[N-1][N-1] + 2 * m[N-1][N-1]，因为路径总和加最大值等价于(总和 - 最大值) + 2*最大值。

状态转移逻辑：

1. 初始化：左上角(0,0)的s[0][0] = 0（总和等于最大值，差值为0），m[0][0] = mat[0][0]。
2. 第一行/第一列：只能从左/上方转移，根据当前元素是否大于路径最大值更新s和m。
3. 其他位置：分别计算从上方和左方转移的候选值，选择能让最终总和更大的状态作为当前位置的最优解。

代码实现 #

public class MaxPathSumWithDoubleMax {
    public static int maxPathSum(int[][] mat) {
        int n = mat.length;
        if (n == 0) return 0;

        // s[i][j] = sum(path) - max(path) 的最大值
        int[][] s = new int[n][n];
        // m[i][j] = 对应s[i][j]路径的最大值
        int[][] m = new int[n][n];

        // 初始化左上角
        s[0][0] = 0;
        m[0][0] = mat[0][0];

        // 填充第一行
        for (int j = 1; j < n; j++) {
            if (mat[0][j] > m[0][j-1]) {
                s[0][j] = s[0][j-1] + m[0][j-1];
                m[0][j] = mat[0][j];
            } else {
                s[0][j] = s[0][j-1] + mat[0][j];
                m[0][j] = m[0][j-1];
            }
        }

        // 填充第一列
        for (int i = 1; i < n; i++) {
            if (mat[i][0] > m[i-1][0]) {
                s[i][0] = s[i-1][0] + m[i-1][0];
                m[i][0] = mat[i][0];
            } else {
                s[i][0] = s[i-1][0] + mat[i][0];
                m[i][0] = m[i-1][0];
            }
        }

        // 填充其他位置
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                // 计算从上方转移的候选值
                int sUp, mUp;
                if (mat[i][j] > m[i-1][j]) {
                    sUp = s[i-1][j] + m[i-1][j];
                    mUp = mat[i][j];
                } else {
                    sUp = s[i-1][j] + mat[i][j];
                    mUp = m[i-1][j];
                }
                int totalUp = sUp + 2 * mUp;

                // 计算从左方转移的候选值
                int sLeft, mLeft;
                if (mat[i][j] > m[i][j-1]) {
                    sLeft = s[i][j-1] + m[i][j-1];
                    mLeft = mat[i][j];
                } else {
                    sLeft = s[i][j-1] + mat[i][j];
                    mLeft = m[i][j-1];
                }
                int totalLeft = sLeft + 2 * mLeft;

                // 选择更优的状态
                if (totalUp > totalLeft) {
                    s[i][j] = sUp;
                    m[i][j] = mUp;
                } else {
                    s[i][j] = sLeft;
                    m[i][j] = mLeft;
                }
            }
        }

        return s[n-1][n-1] + 2 * m[n-1][n-1];
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        System.out.println(maxPathSum(matrix)); // 输出38，与原代码结果一致
    }
}

说明 #

该代码使用两个N*N数组存储状态，时间复杂度为O(N²)，空间复杂度为O(N²)，完全符合题目要求。对于测试用例，输出结果与原代码一致，同时能高效处理更大的N值。

内容的提问来源于stack exchange，提问作者bara