Нахождение минимальной стоимости в 2D матрице

Question

В моем последнем интервью мне был задан вопрос, для какого оптимального подхода я все еще не могу выяснить.

Учитывая двумерную матрицу, с n rows и m columns, мне нужно выбрать по одному предмету из каждой строки и получим минимальную сумму.

Но сложная часть заключалась в том, что при спуске у меня есть два варианта:

1. выбрать элемент в том же столбце как предыдущий .
2. Выбор элемента вне текущего столбца

Таким образом, второй вариант, то есть изменение столбца при переходе вниз, можно выполнить ровно K раз. Мы можем вернуться к тому же столбцу вниз по матрице. Изменение определяется только тогда, когда мы меняем столбец между текущей и следующей строкой.

То, что я пробовал перед интервьюером, было что-то вроде Painting wall problem, где с учетом 3 типов красок мне нужно найти минимальную стоимость, чтобы никакие две вспомогательные стены не окрашены в один цвет. Но там значение m было установлено на 3, и я могу использовать простые cost[i][j] = min(cost[i-1][j-1], cost[i-1][j+1]); // min двух других строк из текущей.

Так что проблема, как и выше, какой подход должен быть, это делает мне кажется, что DP, но я действительно не уверен, что это даст результат.

Answer 1

Эту проблему можно решить, используя подход сверху вниз.

Вы начинаете с места в первом ряду и оттуда идете вниз. У вас есть два варианта:

a) Продолжить в том же столбце - но вы должны принять во внимание, что у вас достаточно строк для переключателей K. Таким образом, ваше условие должно быть remaining_rows >= K, тогда вы можете использовать эту опцию, иначе нет.

b) Переключите ваш столбец на любой другой столбец. Рассмотрим все столбцы.

Из этих двух вариантов взять минимум.

Тогда рекурсивное уравнение будет иметь вид:

getMin(r, c, K) = min( 
                   (R - (r+1) >= K ? getMin(r+1, c, K) + A[r][c] : A[r][c] ),
                   ( for all j != c, j < C: min(getMin(r+1, c, K-1)) )
                  )

, где A - матрица ввода и R - это количество строк, C - это количество столбцов в A.

, и вы берете минимум от getMin(0, c, K ) для всех c = 0 до C

Вы можете запомнить решение для каждого r, c, K.

. Для K = 0 просто пройти вниз по столбцу и получить сумму.

Код в Java:

class Main {
    private static int[][][] dp;

    public static void main(String[] args) {

        int[][] A = { { 0, 1, 2 }, { 4, 3, 1 }, { 6, -2, 5 }, { 1, 4, -3 } };

        int K = 3;
        dp = new int[A.length][A[0].length][K + 1];
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A[0].length; j++) {
                for (int k = 1; k <= K; k++) {
                    dp[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < A[0].length; j++)
            res = Math.min(res, getMin(A, 0, j, K));
        System.out.println(res);
    }

    private static int getMin(int[][] A, int r, int c, int K) {
        int R = A.length, C = A[0].length;
        if (r > R - 1 || c > C - 1)
            return Integer.MAX_VALUE;
        if (K == 0) {
            int sum = 0;
            for (int i = r; i < R; i++)
                sum += A[i][c];
            return sum;
        }
        if (dp[r][c][K] != Integer.MAX_VALUE)
            return dp[r][c][K];
        int min = Integer.MAX_VALUE;
        int rem_rows = R - (r + 1);
        for (int j = 0; j < C; j++) {
            if (j == c && rem_rows >= K) {
                int s = getMin(A, r + 1, j, K);
                if (s != Integer.MAX_VALUE) {
                    min = Math.min(min, s + A[r][c]);
                } else {
                    min = Math.min(min, A[r][c]);
                }

            } else if (j != c) {
                int m = getMin(A, r + 1, j, K - 1);
                if (m != Integer.MAX_VALUE) {
                    min = Math.min(min, m + A[r][c]);
                } else {
                    min = Math.min(min, A[r][c]);
                }
            }
        }
        dp[r][c][K] = min;
        return min;
    }
}

Вы можете играть с живым кодом здесь

Answer 2

Эту проблему можно решить с помощью динамического программирования c: пусть dp[i][j][l] будет минимальной суммой, которую мы можем получить, выбрав несколько чисел из первых i строк, последняя из которых находится в j -ом столбце и имея внесены ровно l изменения столбца. Первоначально dp[0][j][0] = matrix[0][j]. Для обновлений нам нужна следующая формула:

Если мы go с первым вариантом, сделаем так:
dp[i + 1][j][l] = min(dp[i + 1][j][l], dp[i][j][l] + matrix[i + 1][j]).

Если мы go со вторым вариантом, мы должны сделать это для всех new_col != j:
dp[i + 1][new_col][l + 1] = min(dp[i + 1][new_col][l + 1], dp[i][j][l] + matrix[i + 1][new_col])

Результатом будет минимальное значение среди dp[n - 1][j][k] для все j. Общая сложность составляет
O(n * m^2 * k), потому что для всех состояний динамоми c (O(n * m * k)) мы делаем обновления за O(m) время, перебирая new_col для второго типа и O(1) для первого типа .

Мы можем сделать лучше, чем это. Давайте найдем наименьшее dp[i][j][l] для фиксированных i, l, повторяя все возможные j. Предположим, он находится в столбце с номером min_j и значением является x. Для всех j != min_j x будут использоваться обновления второго типа в строке i + 1.

Единственный столбец, который обновляется с использованием другого значения, - это min_j, так как если бы мы перешли от
dp[i][min_j][l] к dp[i + 1][min_j][l + 1], мы бы не переключали столбец. Давайте вычислим
dp[i + 1][min_j][l + 1] путем итерации по всем j != min_j, как мы делали раньше. Общее количество операций составляет O(m).

Сложность будет O(n * m * k), потому что мы делаем O(m) обновлений для всех различных пар i, l и их O(n * k).