Интервью Вопрос об алгоритмах, касающихся матриц

Question

Вам предоставляется матрица N * M, содержащая целочисленные значения. Ваша задача - выбрать одно целое число из каждой строки таким образом, чтобы сумма этих целых чисел была максимальной. Однако вы не можете выбирать два целых числа из соседних строк в одном столбце.

Как я могу решить эту проблему менее чем за O (N ^ M) (или O (M ^ N))

Answer 1

Я предложил два возможных решения: 1. с помощью рекурсии, 2. с помощью DP.

1. Использование Recursion

Я думаю, у вас уже есть это решение. Я сделал рекурсивную функцию, которая проходит через каждую строку в матрице и вызывает рекурсию для каждого столбца. Как вы упомянули, временная сложность будет 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;
}