使用动态规划对矩阵的最大路径求和

Question

给定一个维度为 N * N 的矩阵

mat[][]

，我需要找到给定矩阵从左上角单元格 (0, 0) 到右下角单元格 (N – 1, N – 1) 的路径这样路径中的元素之和是最大的，但我还需要将路径的最大元素添加到路径的总和中（所以我计算每个路径中的最大值两次）。矩阵的任何单元 (i, j) 允许的唯一移动是 (i + 1, j) 或 (i, j + 1)

我需要使用2个大小为(N*N)的数组的动态规划解决方案 时间复杂度为 O(N^2)

这是我尝试过的解决方案，但它不是 O(N^2)

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));
    }
}

这会返回 38，因为路径的最大和是 1->4->7->8->9->9，我们添加 9 两次，因为在每个路径中，我们两次获取最大元素。

Answer 1

将最佳路径（不是所有可能路径）的最大值存储在辅助矩阵的相应单元中，并在计算到该单元的最佳路径时更新它们。

public class Main {

    public static int maxSV(int A[][], int n) {
        int MaxEl[][] = new int[n][n];
        int MaxSum[][] = new int[n][n];
        MaxSum[0][0]=A[0][0];
        MaxEl[0][0]=A[0][0];
        for(int j = 1; j<n;j++) {
            MaxSum[0][j] = MaxSum[0][j-1]+A[0][j];
            MaxEl[0][j] = Math.max(MaxEl[0][j-1], A[0][j]);
            MaxSum[j][0] = MaxSum[j-1][0]+A[j][0];
            MaxEl[j][0] = Math.max(MaxEl[j-1][0], A[j][0]);
        }
        for(int i = 1; i<n;i++) {
            for(int j = 1; j<n; j++) {
                if (MaxSum[i-1][j] >= MaxSum[i][j-1]) {
                        MaxSum[i][j] = MaxSum[i-1][j]+A[i][j];
                        MaxEl[i][j] = Math.max(MaxEl[i-1][j], A[i][j]);
                }
                else {
                        MaxSum[i][j] = MaxSum[i][j-1]+A[i][j];
                        MaxEl[i][j] = Math.max(MaxEl[i][j-1], A[i][j]);
                }
            }   
        }
        return MaxSum[n-1][n-1]+MaxEl[n-1][n-1];
    }
    

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

Answer 2

如果数组是

[[0,2,0], [1,2,2], [4,0,0]]

，这是否给出最佳值？最长的路径是

[0,0]->[0,1]->[1,1]->[1,2]->[2,2]

。它的长度为

6

，在添加其最大元素

8

后变为

2

。然而，路径

[0,0]->[1,0]->[2,0]->[2,1]->[2,2]

的长度只有

5

，但在添加其最大元素

9

后就变成了

4

。因此，后者被认为是最佳路径。