Obegränsad ryggsäck och myntväxlings-DP

I det obegränsade ryggsäcksproblemet kan varje föremål tas med hur många gånger som helst. Tänk på mynt i en automat, inte på en fast hög.

Jämfört med 0/1 är det bara loopriktningen som ändras. För obegränsade föremål itererar du kapaciteten framåt, från låg till hög.

När du går framåt kan dp[w - coin] redan innehålla samma föremål. Den avsiktliga återanvändningen är precis det som gör att du kan ta det igen.

Det klassiska problemet coin change frågar efter det minsta antalet mynt som summerar till ett belopp. Det är obegränsad DP med ett minimum i stället för ett maximum.

Låt dp[a] vara det minsta antalet mynt som behövs för att bilda belopp a. Börja med dp[0] = 0, eftersom noll kräver inga mynt.

Belopp som inte kan nås initieras som oändlighet. Om ett belopp fortfarande är oändligt i slutet kan ingen kombination av mynt bilda det.

För varje mynt försöker du förbättra alla belopp som det kan nå. Använd ett mynt mer än det mindre kvarvarande beloppets bästa värde.

Genom att svepa beloppen uppåt kan dp[a - coin] redan räkna med det här myntet. Det är så ett enda mynt kan bidra flera gånger.

Byt ut min+1 mot en summa för att räkna antalet sätt att bilda varje belopp. En yttre myntloop undviker att räkna ordningar två gånger.

Ditt svar finns i dp[amount]. I minimumvarianten betyder ett oändligt värde att målet inte kan bildas.

Kom ihåg den enda skillnaden: bakåtriktad kapacitet betyder att varje föremål används en gång, framåtriktad betyder obegränsad användning. Samma tabell, motsatt genomgång.

Du ändrade loopen till framåt för obegränsad återanvändning och byggde coin change med min för minsta antalet mynt eller summa för det totala antalet sätt. 💰