有关矩阵的算法访谈问题

Question

将为您提供一个包含整数值的N * M矩阵。您的任务是从每一行中选择一个整数，以使这些整数的总和最大。但是，不允许您从同一列的相邻行中选择两个整数。

如何在小于O（N ^ M）（或O（M ^ N））的范围内解决此问题？

Answer 1

我提出了两种可能的解决方案：1.使用递归，2.使用DP。

1。使用递归

我认为您已经有了此解决方案。我做了一个递归函数，它遍历矩阵的每一行，并为每一列调用递归。正如您提到的，时间复杂度为O（M ^ N），其中N是行数，M是列数。

int getMaxSum(int[][] matrix) {
    return getMax(matrix, 0, -1);
}

int getMax(int[][] matrix, int row, int prevCol) {
    if (row >= matrix.length) return 0;

    int result = Integer.MIN_VALUE;
    for (int i = 0; i < matrix[row].length; i++) {
        if (i == prevCol) continue;

        int sum = getMax(matrix, row+1, i) + matrix[row][i];
        result = Math.max(result, sum);
    }

    return result;
}

2。使用DP

而不是递归遍历所有行和列，我可以使用DP跟踪直到某一行的每一列的最大和。例如，DP[r][c]可以在列c到行r之间具有最大可能的总和。为了实现这一点，我需要遍历输入矩阵中的所有行和列，并且在每个索引处，我还需要遍历前一行（不包括同一列）的最大和。这将导致时间复杂度O（N * M ^ 2），其中N是行数，M是列数。

int getMaxSum(int[][] matrix) {
    if (matrix.length == 0) return 0;

    int[][] maxSumsDP = new int[matrix.length+1][matrix[0].length];
    for (int r = 1; r <= matrix.length; r++) {
        for (int c = 0; c < matrix[r-1].length; c++) {
            int maxPrev = Integer.MIN_VALUE;
            for (int i = 0; i < maxSumDP[r-1].length; i++) {
                if (i == c) continue;

                maxPrev = Math.max(maxPrev, maxSumsDP[r-1][i]);
            }
            maxSumsDP[r][c] = maxPrev + matrix[r-1][c];
        }
    }

    int result = maxSumsDP[maxSumsDP.length-1][0];
    for (int i = 1; i < maxSumsDP[maxSumsDP.length-1].length; i++) {
        result = Math.max(result, maxSumsDP[maxSumsDP.length-1][i]);
    }
    return result;
}