Blind 75 — Вопросы по программированию и техническому интервью — серия объяснений

Проблема:

Объяснение:

Первоначально я думал, что это решение было простым, отсортируйте монеты, а затем просто двигайтесь в обратном направлении от самой большой монеты к самой маленькой, пока сумма не станет 0. Проблема с этим решением, возможно, в том, что сумма больше, чем у самой большой монеты, но вы не можете достичь 0 если используется самая крупная монета. Здесь проблема становится более сложной. Лучше всего работает метод восходящего динамического программирования. Вы можете работать от $ 0,01 (сумма представляет собой цент, а не доллар) до суммы, а затем для каждого целого доллара просматривайте каждую монету, и если монета меньше или равна сумме, добавьте еще одну. монеты к общему количеству монет, использованных для получения предыдущей суммы. После этого цикла верните минимальное количество монет, которое нужно добавить к этой сумме.

Решение для динамического программирования: O(n * k)

Сначала создайте массив, который используется для отслеживания минимального количества монет, необходимого для суммирования суммы. Установите каждый индекс в этом массиве равным сумме плюс один. Это используется во время оператора возврата, чтобы проверить, могут ли монеты суммироваться до суммы, а также определить минимальное количество необходимых монет. Однако, чтобы вычислить сумму, вы должны установить индекс 0 на 0. Это потому, что как только вы достигнете монеты, которая установит эту сумму на 0, вы можете добавить одну монету к счету монет. Теперь выполните цикл от 1 до суммы (n) и для каждой суммы выполните цикл по всем монетам (k). Для каждой монеты вы хотите утверждать, что монета меньше или равна сумме. Если это так, вы хотите установить индекс в массиве на минимум самого себя (если бы работала другая монета, это была бы эта сумма) и 1 плюс количество монет суммы минус монета (количество монет, которое потребовалось, чтобы добраться до предыдущую сумму). Это будет означать, что каждая сумма будет иметь минимальное количество монет, необходимое для достижения этой суммы. После завершения верхнего цикла верните то количество монет, которое потребовалось для достижения суммы, если она не равна сумме плюс 1 (начальное значение). Если оно равно этому значению, верните -1, так как никакая комбинация монет не может достичь этого значения.

class Solution:
 def coinChange(self, coins: List[int], amount: int) -> int:
  dp = [amount + 1] * (amount + 1)
  dp[0] = 0
 
  for a in range(1, amount + 1):
   for c in coins:
    if a — c >= 0:
     dp[a] = min(dp[a], 1 + dp[a — c])
 
  return dp[amount] if dp[amount] != amount + 1 else -1

Информация:

Веб-сайт: nkwade.dev
LinkedIn: linkedin.com/in/nkwade
GitHub: github.com/nkwade
Электронная почта: [email protected]