Изменение монеты - DP

Question

У меня есть небольшая проблема в понимании проблемы с изменением монет в динамическом программировании. Проще говоря, я должен изменить сумму, используя минимальное количество монет.

У меня есть п номиналов монет значений 1 = v1 v2 < < ... < Vn, и мы отмечаем M (J) минимальное количество монет, необходимых, чтобы сделать изменения для суммы у.

В приведенной выше формуле я не понимаю, что означает M (j-vi). vi должно быть максимальным значением монет, используемых в j-1?

Answer 1

Вы делаете груды монет для разных значений j, называемых M (j). Точка M (j - v _i) должна рассмотреть монету величиной v _i, затем в какую кучу вы добавляете ее, чтобы достичь значения j? Куча со значением j - v _i, конечно, потому что это плюс монета, которую вы рассматриваете, теперь добавляет значение j.

Конечно цель состоит в том, чтобы иметь как можно меньше монет, поэтому вы берете самую маленькую кучку, что вы можете продлить, чтобы достичь значения j пути добавления монеты против _I к нему. Это то, что делает min. +1, потому что вы добавляете монету v _i в кучу, чтобы сформировать новую кучу M (j).

Answer 2

Плюс один означает, что вы потребляете еще одну монету, и поэтому общее изменение, которое вы сделаете, уменьшается на величину добавленной монеты, поэтому исходное значение j уменьшается.