DP: State, geçiş, sıra ve reconstruction

DP bir cache numarası değil problem modelidir. Önce state'in tam anlamını yaz: dp[x], x toplamını oluşturmak için minimum coin sayısı olsun. Sonra son kararın olası seçeneklerinden recurrence çıkar; base case ve impossible state'i belirt. Tabulation alt bağımlılıkları önce çözen sırayı ister; memoization yalnız erişilen state'leri çözer.

Minimum coin'de dp[0]=0, dp[x]=min(dp[x−c]+1). Coin'lerin pozitif olması recursion ve tablo ilerlemesi için önemlidir. Yalnız optimum sayıyı bulmak hangi coin'lerin kullanıldığını söylemez; choice/parent tutarak reconstruction yap.

Optimal substructure mevcut olmalı; state gelecekte gerekli bilgiyi kaybetmemelidir. “Sadece son fiyat” yeterli değilse kullanılabilir kapasite veya önceki seçim durumu eklenir. State sayısı×transition maliyeti pratik analizdir. Capacity W'ye bağlı knapsack O(nW), W'nin bit uzunluğuna göre pseudo-polynomial'dir.

DP tasarımını tabloya dök

Coin set {1,3,4}, target 6 için greedy 4+1+1 seçer, üç coin kullanır. Optimum 3+3, iki coin. dp[x] “tam x miktarı için minimum coin sayısı” olsun. dp[0]=0; diğer başlangıçlar +∞. Transition dp[x]=min(dp[x−c]+1), c≤x. x artan sırada gezildiğinde bütün dependency'ler hazırdır. Reachable olmayan state +∞ olarak kalır.

x	0	1	2	3	4	5	6
dp[x]	0	1	2	1	1	2	2

Reconstruction için son seçilen coin'i parent[x] olarak sakla; x'ten coin'i çıkararak sıfıra dön. Tie-break politikası çıktının deterministik olmasını sağlar. Sadece minimum sayı dönmek ile gerçek çözümü dönmek farklı output contracts'tır.

DP'nin doğruluğu state'in optimal substructure'ı yakalamasına bağlıdır. “Gelecek kararları geçmişin hangi bilgisine ihtiyaç duyuyor?” sorusunu sor. Eğer her coin yalnız bir kez kullanılabiliyorsa bu state/transition sınırsız coin probleminden farklıdır. 0/1 knapsack'te bir boyutlu capacity döngüsünü yanlış yönde gezmek aynı item'ı tekrar kullanabilir.

Temel: dp[6] sonucunu elle çıkar. Orta: Parent'larla gerçek coin listesini döndür. İleri: Target ikili yazıldığında O(target·k)'nın neden pseudo-polynomial olduğunu bit uzunluğuyla açıklayıp unreachable ve zero/negative coin input contracts'ını belirt.

def min_coins(coins, target):
    if target < 0 or any(c <= 0 for c in coins): raise ValueError("invalid input")
    dp = [0]+[float("inf")]*target
    for x in range(1,target+1):
        for c in coins:
            if c <= x: dp[x]=min(dp[x],1+dp[x-c])
    return None if dp[target] == float("inf") else dp[target]
assert min_coins([1,3,4],6) == 2