Охватывает ли этот алгоритм все случаи нахождения минимального обмена монет на сумму?

Question

Я пытаюсь решить проблему минимальной замены монет. Вопрос в том: При заданном значении V, если мы хотим внести изменения в V центов, и у нас есть бесконечный запас каждой из монет с ценностями C = {C1, C2, .., Cm}, какое минимальное количество монет для внесения изменения?

Мой алгоритм:

Начиная с массива arr [1..V], где V - это значение:

1. Для всех конфессий инициализируйте arr [d] = 1, так как это базовый случай. Если значение == демонизация монеты, требуется только 1 монета и, следовательно, она является наименьшей

2. Для всех значений из i: 1 ... V: вычислите минимальное количество монет, необходимое для внесения изменений в значение «i». 2.1. Это может быть сделано: Для всех j: 1 .... (i-1) обр [я] = мин (обр [I], обр [J] + обр [I-J]);

3. return arr [V];

Эта логика ошибочна или охватывает все случаи? Большинство решений DP используют двумерный массив, и я не понимаю, почему они использовали бы пространство памяти O (n ^ 2), если это существует и правильно. Спасибо.

Answer 1

Как насчет случаев, когда какое-то значение V не может быть получено?

т.е. у нас есть монеты {5,6,7,8,9}, и мы не можем сделать значения 1,2,3,4. Вы должны инициализировать все значения! = ячейки демонизации в постоянную бесконечности или что-то подобное.

Теперь по той причине, что большинство людей использует O (n ^ 2) памяти:

Эта проблема связана с различными вариантами, наиболее распространенным из которых является то, что вы можете использовать каждую монету только один раз, в этом случае использовать состояние dp [i] [j] - минимальные монеты, которые суммируются с j после рассмотрения первых монет i, кажутся более простыми понять для большинства людей, даже если это можно сделать с помощью O (n) памяти (просто цикл назад)