Размен монет (DP)

Здесь мы рассмотрим вопросы динамического программирования (DP), где нам нужно найти оптимальное решение для всех значений в цели.

Вам дан целочисленный массив coins, представляющий монеты разного номинала, и целочисленный массив amount, представляющий общую сумму денег.

Возвратите наименьшее наименьшее количество монет, необходимое для получения этой суммы. Если эту сумму денег нельзя компенсировать ни одной комбинацией монет, верните -1 .

Вы можете предположить, что у вас есть бесконечное количество монет каждого вида.

Для DP нужно помнить, что нужно определить подзадачу и использовать решение подзадачи для получения ответа. Давайте составим таблицу для вычисления всех возможных комбинаций монет [1, 2, 5] и суммы до 11.

Мы видим, что для создания 0$ нам нужно 0 монет. Чтобы сделать 1$, нам понадобится 1 счет номиналом 1$. Чтобы получить сумму 2$, мы можем использовать 2 счета 1$ или 1 счет 2$ и так далее. Для определенной суммы мы берем min этой суммы и другие комбинации amount-coin +1.

Ярко-желтая строка является оптимальным количеством для каждой суммы.

Код для вычисления этой таблицы:

import math
from typing import List, Dict
from collections import defaultdict

def coin_change_helper(coins: List[int], cache: Dict[int, int], amount: int) -> int:
    if amount in cache:
        return cache[amount]
    if amount == 0:
        return 0

    cache[amount] = math.inf

    for coin in coins:
        if amount - coin >= 0:
            cache[amount] = min(cache[amount], \
                                coin_change_helper(coins, cache, amount-coin)+1)
    return cache[amount]

def coin_change(coins: List[int], amount: int) -> int:
    cache = defaultdict(int)

    res = coin_change_helper(coins, cache, amount)
    return res if res != math.inf else -1

coins = [1, 2, 5]
amount = 11

print(coin_change(coins, amount)) # prints 3

coins1 = [2]
amount1 = 3

print(coin_change(coins1, amount1)) # prints -1

Для рекурсивного шага уже вычисленной суммы мы будем получать значение из cache, поэтому нам не нужно вводить цикл for; то, что до сих пор ломало мне голову, когда я работал над проблемой без дедлайна.

Теперь давайте реализуем восходящий подход:

import math
from typing import List

def coin_change(coins: List[int], amount: int) -> int:
    dp = [math.inf] * (amount+1)
    dp[0] = 0

    for coin in coins:
        for amt in range(1, amount+1):
            if amt - coin >= 0:
                dp[amt] = min(dp[amt], dp[amt-coin]+1)

    return dp[amount] if dp[amount] != math.inf else -1

coins = [1, 2, 5]
amount = 11

print(coin_change(coins, amount)) # prints 3

coins1 = [2]
amount1 = 3

print(coin_change(coins1, amount1)) # prints -1

Мы строим решение подзадачи. Ниже приведена таблица, в которой показано количество монет, необходимое для каждого номинала в [1, 2, 5] на сумму 11.

Мы вернем dp[amount], что равно 3 в последней строке и последнем элементе.

Бонус: если вы этого не заметили, выделенная желтым цветом строка в запомненном табличном значении совпадает с последней строкой в ​​решении dp.

Решим еще одну аналогичную задачу:

Идеальные квадраты

Получив целое число n, верните наименьшее число совершенных квадратных чисел, сумма которых равна n .

Идеальный квадрат – это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются правильными квадратами, а 3 и 11 — нет.

Вот запомненная версия:

import math
import collections
from typing import List

def perfect_square_helper(squares: List[int], cache: List[int], n: int) -> int:
    if n in cache:
        return cache[n]
    
    if n == 0:
        return 0

    cache[n] = math.inf

    for square in squares:
        if n - square >= 0:
            cache[n] = min(cache[n], \
                           perfect_square_helper(squares, cache, n-square)+1)
    print(cache)

    return cache[n]

def perfect_square(n: int) -> int:
    squares = [i**i for i in range(1, int(n**1/2)+1)]
    cache = collections.defaultdict(int)
    res = perfect_square_helper(squares, cache, n)
    return res

n = 12
print(perfect_square(n)) # prints 3

Вот версия снизу вверх:

import math

def perfect_square(n: int) -> int:
    squares = [i**i for i in range(int(n**1/2)+1)]
    dp = [math.inf] * (n+1)
    dp[0] = 0

    for square in squares:
        for i in range(1, n+1):
            if i-square >= 0:
                dp[i] = min(dp[n], dp[i-square]+1)

    # print(dp)
    return dp[-1]

n = 12
print(perfect_square(n)) # prints 3

Реализация такая же! 😵

Это все для этого поста. Надеюсь, вы получаете более мягкое и приятное знакомство с DP.

До следующего раза ✨.

Вдохновение:

• Литкод

Вы можете поддержать меня в Патреоне!