Размен монет и подъём по лестнице с минимальной стоимостью

Задача о размене монет

# Problem examples:
# coins=[1,5,6,9], amount=11 -> 2 (5+6 or 2+9? no: 5+6=11 YES)
# coins=[2],       amount=3  -> -1 (impossible)
# coins=[1,2,5],   amount=11 -> 3 (5+5+1)
# coins=[186,419,83,408], amount=6249 -> 20

# Key choices:
# - Try each coin denomination at each step
# - Minimum coins = 1 + minimum(coins to make amount - coin)
# - If amount < 0: impossible
# - If amount = 0: done (0 coins)

print('Coin change: unbounded knapsack, find minimum count')

Размен монет: вывод рекуррентного соотношения

def coin_change(coins, amount):
    # dp[i] = min coins to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base: 0 coins for amount 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], 1 + dp[i - coin])

    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 6, 9], 11))  # 2
print(coin_change([2], 3))             # -1
print(coin_change([1, 2, 5], 11))      # 3

# Trace dp for coins=[1,5] amount=6:
# dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4, dp[5]=1, dp[6]=2

Размен монет: почему жадный подход не работает

# Greedy failure example:
# coins=[1,3,4], amount=6
# Greedy: 4 (rem=2), 1 (rem=1), 1 (rem=0) -> 3 coins
# Optimal: 3 (rem=3), 3 (rem=0) -> 2 coins

def coin_change_greedy_wrong(coins, amount):
    coins_sorted = sorted(coins, reverse=True)
    count = 0
    for coin in coins_sorted:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

print('Greedy:', coin_change_greedy_wrong([1,3,4], 6))  # 3 (WRONG)
print('DP:    ', coin_change([1,3,4], 6))               # 2 (CORRECT)

Размен монет II: подсчёт способов

def coin_change_ii(coins, amount):
    # dp[i] = number of ways to make amount i
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make amount 0: use no coins

    # Outer loop: coins -- ensures each coin type processed once
    for coin in coins:
        # Inner loop: amounts
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

print(coin_change_ii([1, 2, 5], 5))   # 4: [1,1,1,1,1],[1,1,1,2],[1,2,2],[5]
print(coin_change_ii([2], 3))          # 0: impossible
print(coin_change_ii([10], 10))        # 1

# Key: coin outer, amount inner = COMBINATIONS (unordered)
# Reverse (amount outer, coin inner) = PERMUTATIONS (ordered)

Лестница с минимальной стоимостью: задача

# cost = [10, 15, 20]
# Pay cost[i] to leave step i
# You can step to i+1 or i+2
# Goal: reach top (index 3) with minimum cost

# Path options:
# Start at 0: cost 10, go to 2: cost 20, done -> 30
# Start at 1: cost 15, go to 3: done -> 15  <- OPTIMAL
# Start at 0: cost 10, go to 1: cost 15 -> 25

cost = [10, 15, 20]
# Optimal: start at step 1, pay 15, jump to top -> cost = 15
print('Expected:', 15)

Лестница с минимальной стоимостью: рекуррентное соотношение

def min_cost_climbing_stairs(cost):
    n = len(cost)
    # dp[i] = minimum cost to reach step i
    # Steps 0 to n; step n is the top (goal)
    dp = [0] * (n + 1)
    # dp[0] = 0 (free to start here)
    # dp[1] = 0 (free to start here)
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1],   # step from i-1
                    dp[i-2] + cost[i-2])    # jump from i-2
    return dp[n]

print(min_cost_climbing_stairs([10, 15, 20]))      # 15
print(min_cost_climbing_stairs([1,100,1,1,1,100,1,1,100,1]))  # 6

Лестница с минимальной стоимостью: оптимизация памяти

def min_cost_optimised(cost):
    n = len(cost)
    prev2, prev1 = 0, 0  # dp[0] and dp[1]
    for i in range(2, n + 1):
        curr = min(prev1 + cost[i-1], prev2 + cost[i-2])
        prev2, prev1 = prev1, curr
    return prev1

print(min_cost_optimised([10, 15, 20]))  # 15
print(min_cost_optimised([1,100,1,1,1,100,1,1,100,1]))  # 6

# Alternative: directly use cost array as rolling storage
def min_cost_v2(cost):
    n = len(cost)
    for i in range(2, n):
        cost[i] += min(cost[i-1], cost[i-2])
    return min(cost[-1], cost[-2])

from copy import deepcopy
cost_test = [10,15,20]
print(min_cost_v2(deepcopy(cost_test)))  # 15

Альтернативная формулировка DP

def min_cost_alternative(cost):
    n = len(cost)
    # dp[i] = min cost when starting FROM step i
    # Fill right to left
    dp = cost[:] + [0]  # dp[n] = 0 (already at top)
    for i in range(n - 1, -1, -1):
        # Pay cost[i], then choose i+1 or i+2
        if i + 2 <= n:
            dp[i] = cost[i] + min(dp[i+1], dp[i+2])
        else:
            dp[i] = cost[i] + dp[i+1]
    # Can start at step 0 or step 1
    return min(dp[0], dp[1])

print(min_cost_alternative([10, 15, 20]))  # 15
print(min_cost_alternative([1,100,1,1,1,100,1,1,100,1]))  # 6

Связь между разменом монет и лестницей

# Shared pattern:
# dp[state] = optimise(dp[prev_state_1] + cost_1,
#                      dp[prev_state_2] + cost_2, ...)

# Coin change:  dp[amount] = min(1 + dp[amount - coin] for coin in coins)
# Min stair:    dp[step]   = min(cost[step-1]+dp[step-1], cost[step-2]+dp[step-2])
# Max path sum: dp[cell]   = max(dp[top], dp[left]) + grid[cell]
# House robber: dp[house]  = max(dp[house-1], dp[house-2] + value[house])

# All four are the SAME pattern with different:
# - State representation
# - Number of choices per state
# - Objective (min/max)
# - Transition cost
print('DP pattern: state + choices + objective + cost = template')

Минимальное количество полных квадратов

import math

def num_squares(n):
    # Generate all perfect squares up to n
    squares = [i*i for i in range(1, int(math.sqrt(n)) + 1)]
    # Coin change with squares as 'coins'
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        for sq in squares:
            if i >= sq:
                dp[i] = min(dp[i], 1 + dp[i - sq])
    return dp[n]

print(num_squares(12))  # 3: 4+4+4
print(num_squares(13))  # 2: 4+9
print(num_squares(1))   # 1: 1

Отладка DP: распространённые ошибки

# Common DP debugging checklist:
# 1. Base case: what is dp[0]? dp[1]? Are they correct?
# 2. State definition: write it in English before coding
# 3. Recurrence: trace manually on a 3-element example
# 4. Fill order: dependency arrows point left/up? Fill left/up first
# 5. Infinity check: return -1 or 0 when dp[target] == inf?
# 6. Array bounds: dp has size n+1 for 0..n, or n for 0..n-1?

# Quick test template:
def test_coin_change():
    assert coin_change([1], 0) == 0     # base case
    assert coin_change([1], 1) == 1     # single coin
    assert coin_change([2], 3) == -1    # impossible
    assert coin_change([1,5,6,9], 11) == 2
    print('All tests passed!')

test_coin_change()

Проверка знаний

Итоги урока