Coin Chane - Dynami c Программирование - Как читать все решения из таблицы DP

Question

Я видел разные решения одной и той же проблемы, но ни один из них, похоже, не использовал подход, который я использовал. Итак, здесь я пытаюсь решить классическую проблему обмена монет с помощью динамического подхода «снизу вверх» с использованием таблицы DP.

    int[][] dp = new int[nums.length+1][target+1];
    for (int i = 0; i <= nums.length; ++i)
        dp[i][0] = 1;

    for (int i = 1; i < dp.length; ++i) {
        for (int j = 1; j < dp[i].length; ++j) {
            if (nums[i-1] <= j)
                dp[i][j] = dp[i-1][j] + dp[i][j-nums[i-1]];
            else
                dp[i][j] = dp[i-1][j];
        }
    }

Приведенный выше код создает таблицу. Ради интереса, если у меня есть {2,3,5} монет и я хочу обменять 8, таблица будет выглядеть следующим образом:

1 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 1
1 0 1 1 1 1 2 1 2
1 0 1 1 1 2 2 2 3

Для вышеизложенного следующий метод, похоже, работает хорошо:

current <- 4
while (current > 0) do
    i <- current
    j <- 8
    while (j > 0) do
        if (dp[i][j] != dp[i-1][j]) then
            nums[i-1] is part of the current solution
            j <- j-1
        else
            i <- i-1
        end
    end
    current <- current-1
end

Проходя по приведенному выше примеру, мы получаем следующие решения:

1) [5,3]
2) [3,3,2]
3) [2,2,2,2]

Что здорово! По крайней мере, я думал, пока не попробовал: {1,2} с Т = 4. Для этого таблица выглядит следующим образом:

1 0 0 0 0
1 1 1 1 1
1 1 2 2 3

С помощью приведенного выше алгоритма для печати всех решений я получаю только:

[2,2]
[1,1,1,1]

Что означает, что я не восстановлюсь [2,1, 1]. Таким образом, этот вопрос не о обобщенном c, как печатать решения для различных подходов к этой проблеме, а о том, как я могу прочитать приведенную выше таблицу DP, чтобы найти все решения.

Answer 1

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

private List<List<Integer>> readSolutions(int[] nums, int[][] dp, int currentRow, int currentColumn, List<Integer> partialSolution) {
    if (currentRow == 0) {
        return new ArrayList<>();
    }

    if (currentColumn == 0) {
        return new ArrayList<List<Integer>>(Collections.singleton(partialSolution));
    }

    List<List<Integer>> solutions = new ArrayList<>();
    if (dp[currentRow][currentColumn] != dp[currentRow-1][currentColumn]) {
        List<Integer> newSolution = new ArrayList<>(partialSolution);
        newSolution.add(nums[currentRow-1]);
        solutions.addAll(readSolutions(nums, dp, currentRow, currentColumn-nums[currentRow-1], newSolution));
        solutions.addAll(readSolutions(nums, dp, currentRow-1, currentColumn, partialSolution));

        return solutions;
    }

    return readSolutions(nums, dp, currentRow-1, currentColumn, partialSolution);
}

Logi c, с другой стороны, прост. Возьмите приведенную выше таблицу, например:

  0 1 2 3 4
0 1 0 0 0 0
1 1 1 1 1 1
2 1 1 2 2 3

Чтобы получить единственное решение, мы начинаем с правого нижнего угла. Если значение совпадает со значением непосредственно над нами, мы движемся вверх. Если этого не произойдет, мы переместимся влево на величину, соответствующую строке, в которой мы находимся. С другой стороны, чтобы сгенерировать все ответы из приведенной выше таблицы ...

• мы находимся в некотором position (i, j)
• , если значение в (i-1, j) совпадает с (i, j), мы делаем рекурсивный вызов (i-1, j)
• если значения не совпадают, у нас есть 2 варианта ...
• мы можем использовать число, соответствующее текущей строке, и вернуться в (i, jn)
• мы можем пропустить номер и проверьте, можем ли мы создать (i, j) вместо этого, используя вместо этого рекурсивный вызов (i-1, j).
• если мы достигнем первой строки, мы возвращаем пустой список
• если мы дойдем до первого столбца, мы вернем то, что уже нашли, у которого будет целевая сумма.

выглядит ужасно хорошо, но работает, как и ожидалось.