The UK coin system uses the eight denominations \(C=\{1,2,5,10,20,50,100,200\}\), measured in pence. The problem asks for the number of unordered collections of these coins whose total is 200 pence, that is, £2.
Equivalently, we must count the non-negative integer solutions of
$$n_1+2n_2+5n_5+10n_{10}+20n_{20}+50n_{50}+100n_{100}+200n_{200}=200.$$
The key word is unordered: only the multiset of coins matters, not the order in which coins are listed. The implementations compute this count exactly, and the final value is \(73682\).
The clean way to count unordered coin combinations is to process the denominations one by one and keep track of how many totals are reachable with the denominations seen so far.
Write the sorted denominations as \(c_1=1,c_2=2,\dots,c_8=200\). Let \(A_j(t)\) denote the number of ways to make \(t\) pence using only the first \(j\) denominations. Then \(A_j(t)\) counts restricted partitions of \(t\): parts may repeat, but each part must belong to \(\{c_1,\dots,c_j\}\).
The base conditions are immediate:
$$A_0(0)=1,\qquad A_0(t)=0\quad (t>0).$$
There is exactly one way to make 0 with no coins, namely the empty choice, and no way to make a positive amount with no denominations available.
Fix \(j\) and consider amount \(t\). Every valid combination counted by \(A_j(t)\) falls into exactly one of two classes.
The first class uses no coin of value \(c_j\), so it contributes \(A_{j-1}(t)\). The second class uses at least one \(c_j\); after removing one such coin, what remains is a valid combination for \(t-c_j\) that may still use \(c_j\), so it contributes \(A_j(t-c_j)\).
Therefore, for \(t\ge c_j\),
$$A_j(t)=A_{j-1}(t)+A_j(t-c_j).$$
For \(t<c_j\), the denomination \(c_j\) cannot appear at all, so \(A_j(t)=A_{j-1}(t)\). This recurrence is the mathematical core of the solution.
The recurrence only needs the previous denomination set and the current denomination set at smaller amounts, so the usual two-dimensional table can be collapsed to one dimension. Maintain an array \(W[0],W[1],\dots,W[200]\), and after finishing denomination \(c_j\), interpret \(W[t]\) as \(A_j(t)\).
Initially \(W[0]=1\) and every other entry is 0. When processing coin \(c\), update amounts in ascending order:
$$W[t]\leftarrow W[t]+W[t-c]\qquad (t=c,c+1,\dots,200).$$
This order is crucial. Before the assignment, \(W[t]\) still represents the count without the current coin, namely \(A_{j-1}(t)\). Because \(t\) increases, the entry \(W[t-c]\) has already been updated for the current coin and therefore equals \(A_j(t-c)\). After the addition, \(W[t]\) becomes exactly \(A_j(t)\).
If the amounts were scanned in descending order instead, the update would forbid repeated use of the same denomination and would solve a different problem. The ascending sweep is precisely what enforces “unlimited copies of each coin, but counted without order.”
The implementations verify that the number of ways to make 10 pence is \(11\). That value illustrates the recurrence nicely.
After processing 1p and 2p coins, the number of ways to make 10 is \(6\), corresponding to 0, 1, 2, 3, 4, or 5 copies of the 2p coin. When the 5p coin is processed, the update adds the number of ways to make 5, which is \(4\), so the count for 10 rises from \(6\) to \(10\). Finally, processing the 10p coin adds \(W[0]=1\), producing \(11\).
In direct combinatorial terms, those 11 combinations are: one 10p coin; two 5p coins; one 5p coin plus any of the 3 ways to make 5 from \(\{1,2\}\); or no 5p coin plus any of the 6 ways to make 10 from \(\{1,2\}\). The dynamic program packages exactly that case split into repeated local updates.
The same answer can be described as a coefficient extraction problem. Each denomination \(c\) contributes the geometric series
$$1+x^c+x^{2c}+x^{3c}+\cdots=\frac{1}{1-x^c},$$
because we may choose 0, 1, 2, 3, ... copies of that coin. Hence the number of valid £2 combinations is the coefficient of \(x^{200}\) in
$$\prod_{c\in C}\frac{1}{1-x^c} =\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})}.$$
The dynamic program is simply a practical way to build this product while discarding coefficients above degree 200, which are irrelevant for the target amount.
The C++, Python, and Java implementations store the eight UK denominations in ascending order, default the target to 200, and allocate an array of length 201. The entry for amount 0 is set to 1, and every other entry starts at 0.
For each coin value, the implementation scans all reachable amounts from that coin up to the target and adds the count from the smaller amount. After the 1p pass, every amount has exactly one representation. Each later pass adds the representations that use at least one coin of the newly processed denomination.
Before printing the main result, the implementations verify two small benchmark cases: 4 ways for 5 pence and 11 ways for 10 pence. Those checks confirm both the recurrence and the loop order. The final answer is then read directly from the entry for 200 pence, which is \(73682\).
For \(m\) denominations and target \(T\), the method runs in \(O(mT)\) time and uses \(O(T)\) space. Here \(m=8\) and \(T=200\), so the array has only 201 entries.
More concretely, the inner addition is executed exactly
$$\sum_{c\in C}(200-c+1)=1220$$
times. That is why all three implementations finish essentially instantly for Problem 31.
Im Vereinigten Königreich stehen die acht Münzwerte \(C=\{1,2,5,10,20,50,100,200\}\) Pence zur Verfügung. Gesucht ist die Anzahl ungeordneter Münzmengen mit Gesamtsumme 200 Pence, also £2.
Äquivalent zählen wir die nichtnegativen ganzzahligen Lösungen von
$$n_1+2n_2+5n_5+10n_{10}+20n_{20}+50n_{50}+100n_{100}+200n_{200}=200.$$
Entscheidend ist, dass die Reihenfolge der Münzen keine Rolle spielt. Nur wie viele Münzen jeder Sorte gewählt werden, ist relevant. Die Implementierungen berechnen diesen Wert exakt; das Ergebnis ist \(73682\).
Der natürliche Zugang ist, die Münzwerte der Reihe nach zu verarbeiten und für jeden Zwischenbetrag zu speichern, wie viele Darstellungen mit den bisher erlaubten Münzen möglich sind.
Seien die sortierten Münzwerte \(c_1=1,c_2=2,\dots,c_8=200\). Wir definieren \(A_j(t)\) als die Anzahl der Möglichkeiten, \(t\) Pence nur mit den ersten \(j\) Münzwerten zu bilden. Damit zählt \(A_j(t)\) beschränkte Partitionen von \(t\): Wiederholungen sind erlaubt, aber nur Werte aus \(\{c_1,\dots,c_j\}\).
Die Anfangswerte lauten
$$A_0(0)=1,\qquad A_0(t)=0\quad (t>0).$$
Mit keiner einzigen Münzsorte gibt es genau eine Darstellung der 0, nämlich die leere Auswahl, und keine Darstellung eines positiven Betrags.
Fixiere \(j\) und einen Betrag \(t\). Jede Darstellung, die in \(A_j(t)\) gezählt wird, gehört genau zu einer von zwei Klassen.
Entweder kommt die Münze \(c_j\) gar nicht vor; dann zählen wir \(A_{j-1}(t)\). Oder sie kommt mindestens einmal vor; entfernt man eine solche Münze, bleibt eine Darstellung von \(t-c_j\), die weiterhin \(c_j\) benutzen darf. Das liefert \(A_j(t-c_j)\).
Für \(t\ge c_j\) gilt also
$$A_j(t)=A_{j-1}(t)+A_j(t-c_j).$$
Für \(t<c_j\) kann \(c_j\) nicht auftreten, also ist \(A_j(t)=A_{j-1}(t)\). Genau diese Rekursion steckt in allen drei Programmen.
Die Rekursion benötigt nur die vorherige Münzmenge und den aktuellen Zustand bei kleineren Beträgen. Deshalb genügt ein eindimensionales Feld \(W[0],W[1],\dots,W[200]\). Nach Abschluss des Münzwerts \(c_j\) interpretieren wir \(W[t]\) als \(A_j(t)\).
Anfangs ist \(W[0]=1\) und jeder andere Eintrag 0. Beim Verarbeiten einer Münze \(c\) wird für aufsteigende Beträge aktualisiert:
$$W[t]\leftarrow W[t]+W[t-c]\qquad (t=c,c+1,\dots,200).$$
Die aufsteigende Reihenfolge ist der entscheidende Punkt. Vor dem Update steht \(W[t]\) noch für \(A_{j-1}(t)\). Weil \(t\) von klein nach groß läuft, ist \(W[t-c]\) bereits mit derselben Münze aktualisiert und entspricht daher \(A_j(t-c)\). Nach der Addition ist \(W[t]\) genau gleich \(A_j(t)\).
Ein absteigender Durchlauf würde stattdessen erzwingen, dass jede Münze höchstens einmal verwendet wird. Das wäre ein anderes Problem. Der vorliegende Code zählt unbegrenzte Münzanzahlen, aber jede Kombination nur ein einziges Mal.
Die Implementierungen prüfen als Kontrollwert, dass es für 10 Pence genau \(11\) Möglichkeiten gibt. Dieser kleine Fall zeigt die Rekursion sehr klar.
Nach der Verarbeitung von 1p und 2p gibt es \(6\) Darstellungen von 10, entsprechend 0 bis 5 Zweipence-Münzen. Wenn die 5p-Münze hinzukommt, wird die Anzahl der Darstellungen von 5 addiert; dieser Wert ist \(4\). Damit steigt die Zahl für 10 von \(6\) auf \(10\). Danach liefert die 10p-Münze noch einmal \(W[0]=1\), also insgesamt \(11\).
Kombinatorisch kann man dieselbe Zahl so zerlegen: eine 10p-Münze; zwei 5p-Münzen; eine 5p-Münze plus eine der 3 Darstellungen von 5 mit \(\{1,2\}\); oder gar keine 5p-Münze plus eine der 6 Darstellungen von 10 mit \(\{1,2\}\). Die Dynamik der Tabelle fasst genau diese Fallunterscheidung zusammen.
Dasselbe Zählproblem kann als Koeffizientenextraktion formuliert werden. Jeder Münzwert \(c\) trägt die geometrische Reihe
$$1+x^c+x^{2c}+x^{3c}+\cdots=\frac{1}{1-x^c}$$
bei, weil 0, 1, 2, 3, ... Münzen dieses Werts erlaubt sind. Die gesuchte Anzahl ist also der Koeffizient von \(x^{200}\) in
$$\prod_{c\in C}\frac{1}{1-x^c} =\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})}.$$
Die dynamische Programmierung ist hier nichts anderes als eine effiziente Methode, dieses Produkt bis zum Grad 200 auszumultiplizieren und nur die relevanten Koeffizienten zu behalten.
Die C++-, Python- und Java-Implementierungen speichern die acht Münzwerte in aufsteigender Reihenfolge, setzen den Zielbetrag standardmäßig auf 200 und legen ein Feld der Länge 201 an. Der Eintrag für Betrag 0 wird auf 1 gesetzt, alle anderen auf 0.
Für jeden Münzwert wird über alle erreichbaren Beträge von diesem Wert bis zum Ziel iteriert, und jeweils der Wert des kleineren Betrags addiert. Nach dem 1p-Durchlauf hat jeder Betrag genau eine Darstellung. Jeder weitere Durchlauf ergänzt die Darstellungen, die mindestens eine Münze des gerade behandelten Werts enthalten.
Bevor das Hauptergebnis ausgegeben wird, prüfen die Programme zwei kleine Testfälle: 4 Möglichkeiten für 5 Pence und 11 Möglichkeiten für 10 Pence. Diese Prüfungen bestätigen sowohl die Rekursion als auch die richtige Schleifenreihenfolge. Anschließend wird direkt der Eintrag für 200 Pence ausgegeben, also \(73682\).
Für \(m\) Münzwerte und Zielbetrag \(T\) beträgt die Laufzeit \(O(mT)\), der Speicherbedarf \(O(T)\). Hier sind \(m=8\) und \(T=200\), also umfasst das Feld nur 201 Einträge.
Noch konkreter wird die innere Addition genau
$$\sum_{c\in C}(200-c+1)=1220$$
Mal ausgeführt. Deshalb laufen alle drei Implementierungen für Problem 31 praktisch sofort durch.
Birleşik Krallık'ta kullanılan sekiz madeni para değeri \(C=\{1,2,5,10,20,50,100,200\}\) pence'tir. Soru, toplamı 200 pence yani £2 olan sırasız madeni para çokluklarının sayısını istemektedir.
Eşdeğer olarak şu denklemin negatif olmayan tamsayı çözümlerini sayıyoruz:
$$n_1+2n_2+5n_5+10n_{10}+20n_{20}+50n_{50}+100n_{100}+200n_{200}=200.$$
Buradaki kritik nokta, sıranın önemsiz olmasıdır. Yalnızca her kupürden kaç tane seçildiği önemlidir. Uygulamalar bu sayıyı tam olarak hesaplar ve sonuç \(73682\)'dir.
Bu problemi temiz biçimde çözmenin yolu, madeni para değerlerini küçükten büyüğe işleyip o ana kadar izin verilen kupürlerle her ara toplamın kaç farklı şekilde elde edildiğini tutmaktır.
Sıralı kupürleri \(c_1=1,c_2=2,\dots,c_8=200\) olarak yazalım. \(A_j(t)\), yalnızca ilk \(j\) kupürü kullanarak \(t\) pence elde etmenin yol sayısı olsun. Böylece \(A_j(t)\), \(t\)'nin kısıtlı bölümlemelerini sayar: tekrar serbesttir, fakat parçalar yalnızca \(\{c_1,\dots,c_j\}\) kümesinden gelebilir.
Başlangıç koşulları şunlardır:
$$A_0(0)=1,\qquad A_0(t)=0\quad (t>0).$$
Hiç kupür yokken 0 toplamını elde etmenin tek yolu boş seçimdir; pozitif bir toplamı elde etmenin ise hiçbir yolu yoktur.
Bir \(j\) ve bir \(t\) sabitleyelim. \(A_j(t)\) içinde sayılan her çözüm tam olarak iki sınıftan birine aittir.
Ya \(c_j\) değerli hiç madeni para kullanılmaz; bu durumda katkı \(A_{j-1}(t)\) olur. Ya da en az bir tane \(c_j\) kullanılır; bir tanesini çıkardığımızda geriye, hâlâ \(c_j\) kullanabilen, \(t-c_j\) toplamlı bir çözüm kalır. Bunun katkısı \(A_j(t-c_j)\)'dir.
Dolayısıyla \(t\ge c_j\) için
$$A_j(t)=A_{j-1}(t)+A_j(t-c_j).$$
\(t<c_j\) olduğunda ise bu kupür hiç kullanılamaz, dolayısıyla \(A_j(t)=A_{j-1}(t)\) olur. Çözümün matematiksel çekirdeği tam olarak bu yinelemedir.
Yineleme yalnızca bir önceki kupür kümesini ve mevcut kupür için daha küçük toplamları gerektirdiğinden iki boyutlu tabloyu tek boyuta indirebiliriz. \(W[0],W[1],\dots,W[200]\) dizisini tutalım ve \(c_j\) işlendiğinde \(W[t]\)'yi \(A_j(t)\) olarak yorumlayalım.
Başlangıçta \(W[0]=1\), diğer tüm girişler 0'dır. Bir \(c\) kupürü işlenirken toplamlar artan sırayla güncellenir:
$$W[t]\leftarrow W[t]+W[t-c]\qquad (t=c,c+1,\dots,200).$$
Artan sıra burada belirleyicidir. Güncellemeden önce \(W[t]\), hâlâ \(A_{j-1}(t)\)'yi temsil eder. \(t\) küçükten büyüğe gittiği için \(W[t-c]\) aynı kupürle zaten güncellenmiştir ve \(A_j(t-c)\)'ye eşittir. Toplama yapıldıktan sonra \(W[t]\) tam olarak \(A_j(t)\) olur.
Eğer toplamlar azalan sırayla gezilseydi aynı kupürün tekrar kullanılmasına izin verilmezdi; bu da farklı bir problem olurdu. Buradaki artan tarama, “her kupürden sınırsız adet kullanılabilir ama her kombinasyon bir kez sayılır” koşulunu doğru biçimde uygular.
Uygulamalar küçük bir kontrol olarak 10 pence için cevabın \(11\) olduğunu doğrular. Bu değer yinelemenin nasıl çalıştığını açıkça gösterir.
1p ve 2p kupürleri işlendiğinde 10 toplamı için \(6\) yol vardır; bunlar 0'dan 5'e kadar farklı sayıda 2p kullanmaya karşılık gelir. 5p kupürü işlendiğinde 10 için sayıya, 5'i oluşturma sayısı olan \(4\) eklenir; böylece değer \(6\)'dan \(10\)'a çıkar. Son olarak 10p kupürü \(W[0]=1\) kadar ek katkı yapar ve sonuç \(11\) olur.
Bunu doğrudan ayırarak da görebiliriz: bir tane 10p; iki tane 5p; bir tane 5p artı \(\{1,2\}\) ile 5 yapmanın 3 yolu; ya da hiç 5p kullanmadan \(\{1,2\}\) ile 10 yapmanın 6 yolu. Dinamik programlama bu ayrımı yerel güncellemelere dönüştürür.
Aynı sayım, katsayı çıkarma problemi olarak da yazılabilir. Her \(c\) kupürü şu geometrik seriyi verir:
$$1+x^c+x^{2c}+x^{3c}+\cdots=\frac{1}{1-x^c},$$
çünkü bu kupürden 0, 1, 2, 3, ... adet seçilebilir. O halde aradığımız sayı,
$$\prod_{c\in C}\frac{1}{1-x^c} =\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})}$$
ifadesindeki \(x^{200}\) katsayısıdır. Dinamik programlama, bu çarpımı 200. dereceye kadar pratik biçimde oluşturan bir katsayı hesabıdır.
C++, Python ve Java uygulamaları sekiz İngiliz kupürünü artan sırada saklar, hedefi varsayılan olarak 200 alır ve uzunluğu 201 olan bir dizi ayırır. 0 toplamı için giriş 1 yapılır, diğerleri 0'dır.
Her madeni para değeri için, o değerden hedefe kadar tüm toplamlar gezilir ve daha küçük toplamın sayısı eklenir. 1p geçişinden sonra her toplamın tam bir gösterimi vardır. Sonraki her geçiş, yeni kupürü en az bir kez kullanan gösterimleri ekler.
Ana sonuç yazdırılmadan önce iki küçük kontrol çalıştırılır: 5 pence için 4 yol ve 10 pence için 11 yol. Bu kontroller hem yinelemenin hem de döngü sırasının doğru olduğunu gösterir. Ardından 200 pence girişindeki değer doğrudan yazdırılır; bu da \(73682\)'dir.
\(m\) kupür ve hedef \(T\) için yöntem \(O(mT)\) zamanda çalışır ve \(O(T)\) bellek kullanır. Bu problemde \(m=8\) ve \(T=200\) olduğundan dizide yalnızca 201 giriş vardır.
Daha somut olarak, iç toplama tam
$$\sum_{c\in C}(200-c+1)=1220$$
kez yürütülür. Bu yüzden üç uygulama da Problem 31'i neredeyse anında çözer.
En el sistema monetario británico aparecen ocho denominaciones, \(C=\{1,2,5,10,20,50,100,200\}\), medidas en peniques. La pregunta es cuántos multiconjuntos no ordenados de esas monedas suman 200 peniques, es decir, £2.
De forma equivalente, hay que contar las soluciones enteras no negativas de
$$n_1+2n_2+5n_5+10n_{10}+20n_{20}+50n_{50}+100n_{100}+200n_{200}=200.$$
La palabra importante es no ordenados: solo importa cuántas monedas de cada tipo se usan, no el orden en que aparezcan. Las implementaciones calculan este valor exactamente, y el resultado final es \(73682\).
La manera natural de contar combinaciones sin orden es procesar las denominaciones una a una y mantener, para cada cantidad intermedia, cuántas formas existen usando solo las denominaciones ya permitidas.
Escribamos las denominaciones ordenadas como \(c_1=1,c_2=2,\dots,c_8=200\). Definimos \(A_j(t)\) como el número de formas de obtener \(t\) peniques usando únicamente las primeras \(j\) denominaciones. Así, \(A_j(t)\) cuenta particiones restringidas de \(t\): se pueden repetir piezas, pero cada pieza debe pertenecer a \(\{c_1,\dots,c_j\}\).
Las condiciones iniciales son
$$A_0(0)=1,\qquad A_0(t)=0\quad (t>0).$$
Con cero tipos de moneda hay exactamente una manera de formar 0, la elección vacía, y ninguna manera de formar una cantidad positiva.
Fijemos \(j\) y una cantidad \(t\). Toda combinación contada por \(A_j(t)\) cae exactamente en una de dos clases.
O bien no usa ninguna moneda de valor \(c_j\), lo que aporta \(A_{j-1}(t)\), o bien usa al menos una. En ese segundo caso, si quitamos una moneda \(c_j\), queda una combinación válida para \(t-c_j\) que todavía puede usar más monedas \(c_j\). Esa parte aporta \(A_j(t-c_j)\).
Por tanto, para \(t\ge c_j\),
$$A_j(t)=A_{j-1}(t)+A_j(t-c_j).$$
Si \(t<c_j\), la denominación \(c_j\) no puede aparecer y entonces \(A_j(t)=A_{j-1}(t)\). Esa es la recurrencia exacta que implementa el código.
La recurrencia solo necesita la fila anterior y la fila actual en cantidades más pequeñas, así que la tabla bidimensional puede comprimirse en un único arreglo \(W[0],W[1],\dots,W[200]\). Tras terminar la denominación \(c_j\), interpretamos \(W[t]\) como \(A_j(t)\).
Al principio, \(W[0]=1\) y el resto de entradas es 0. Al procesar una moneda \(c\), se actualiza en orden ascendente:
$$W[t]\leftarrow W[t]+W[t-c]\qquad (t=c,c+1,\dots,200).$$
El orden ascendente es esencial. Antes de la asignación, \(W[t]\) todavía representa \(A_{j-1}(t)\). Como \(t\) aumenta, la entrada \(W[t-c]\) ya fue actualizada con la moneda actual y por tanto es \(A_j(t-c)\). Después de sumar, \(W[t]\) pasa a ser exactamente \(A_j(t)\).
Si los importes se recorrieran en orden descendente, se impediría reutilizar la misma moneda varias veces y se resolvería otro problema distinto. El barrido ascendente es justo lo que permite copias ilimitadas de cada denominación sin contar permutaciones.
Las implementaciones comprueban como referencia que el número de formas de obtener 10 peniques es \(11\). Ese caso pequeño ilustra muy bien la recurrencia.
Después de procesar 1p y 2p, existen \(6\) formas de obtener 10, correspondientes a usar 0, 1, 2, 3, 4 o 5 monedas de 2p. Al introducir la moneda de 5p, se añade el número de formas de obtener 5, que es \(4\); por eso el conteo para 10 sube de \(6\) a \(10\). Finalmente, al procesar 10p se añade \(W[0]=1\), y se llega a \(11\).
Dicho de manera combinatoria, esas 11 combinaciones son: una moneda de 10p; dos de 5p; una de 5p más una de las 3 formas de hacer 5 con \(\{1,2\}\); o ninguna de 5p y una de las 6 formas de hacer 10 con \(\{1,2\}\). La programación dinámica encapsula exactamente esa separación de casos.
El mismo conteo puede verse como extracción de coeficientes. Cada denominación \(c\) aporta la serie geométrica
$$1+x^c+x^{2c}+x^{3c}+\cdots=\frac{1}{1-x^c},$$
porque se pueden elegir 0, 1, 2, 3, ... monedas de ese valor. Por tanto, el número buscado es el coeficiente de \(x^{200}\) en
$$\prod_{c\in C}\frac{1}{1-x^c} =\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})}.$$
El programa dinámico no hace más que construir ese producto hasta grado 200 y conservar solo los coeficientes relevantes para la cantidad objetivo.
Las implementaciones en C++, Python y Java almacenan las ocho denominaciones británicas en orden ascendente, toman 200 como objetivo por defecto y reservan un arreglo de longitud 201. La entrada correspondiente al importe 0 se inicializa con 1 y todas las demás con 0.
Para cada moneda, la implementación recorre todos los importes desde ese valor hasta el objetivo y suma el conteo del importe menor. Tras la pasada de 1p, cada cantidad tiene exactamente una representación. Cada pasada posterior añade las representaciones que usan al menos una moneda de la nueva denominación.
Antes de imprimir el resultado principal, se verifican dos casos pequeños: 4 maneras para 5 peniques y 11 maneras para 10 peniques. Esas comprobaciones validan tanto la recurrencia como el orden correcto de los bucles. Después se imprime directamente la entrada correspondiente a 200 peniques, que vale \(73682\).
Con \(m\) denominaciones y objetivo \(T\), el método cuesta \(O(mT)\) tiempo y \(O(T)\) memoria. Aquí \(m=8\) y \(T=200\), así que el arreglo tiene solo 201 posiciones.
De forma más concreta, la suma interior se ejecuta exactamente
$$\sum_{c\in C}(200-c+1)=1220$$
veces. Por eso las tres implementaciones resuelven el Problema 31 de manera prácticamente instantánea.
英国硬币体系包含八种面额，记为 \(C=\{1,2,5,10,20,50,100,200\}\)，单位都是便士。题目要求的是：有多少种无序的硬币多重集，其总和恰好是 200 便士，也就是 £2。
等价地说，我们需要计算下面这个方程的非负整数解个数：
$$n_1+2n_2+5n_5+10n_{10}+20n_{20}+50n_{50}+100n_{100}+200n_{200}=200.$$
这里最重要的条件是“无序”。只关心每种硬币用了多少枚，不关心这些硬币按什么顺序摆放。三个实现都精确算出了这个数量，最终结果是 \(73682\)。
这道题最自然的思路，是把面额从小到大依次加入，并在每一步维护“只用当前已经允许的面额，凑出每个中间金额的方法数”。
把排好序的面额写成 \(c_1=1,c_2=2,\dots,c_8=200\)。定义 \(A_j(t)\) 为“只使用前 \(j\) 种面额时，凑出 \(t\) 便士的方法数”。这样一来，\(A_j(t)\) 本质上就是 \(t\) 的受限整数拆分数：部件可以重复，但每个部件只能来自 \(\{c_1,\dots,c_j\}\)。
初始条件非常直接：
$$A_0(0)=1,\qquad A_0(t)=0\quad (t>0).$$
没有任何面额时，凑出 0 只有一种办法，就是空选择；而凑出正数则完全不可能。
固定 \(j\) 和金额 \(t\)。任何一个被 \(A_j(t)\) 统计到的组合，都恰好落入下面两类之一。
第一类完全不使用面额 \(c_j\)，这部分贡献 \(A_{j-1}(t)\)。第二类至少使用一枚 \(c_j\)。如果从这类组合里拿掉一枚 \(c_j\)，剩下的仍然是一个凑出 \(t-c_j\) 的合法组合，而且它仍然允许继续使用 \(c_j\)。因此第二类贡献 \(A_j(t-c_j)\)。
于是当 \(t\ge c_j\) 时，有递推式
$$A_j(t)=A_{j-1}(t)+A_j(t-c_j).$$
如果 \(t<c_j\)，那么面额 \(c_j\) 根本不可能出现，所以 \(A_j(t)=A_{j-1}(t)\)。这就是整个解法真正使用的数学核心。
上面的递推只依赖上一层面额以及当前面额下更小的金额，因此二维表可以压缩成一维。维护数组 \(W[0],W[1],\dots,W[200]\)，并规定：在处理完面额 \(c_j\) 之后，\(W[t]\) 就表示 \(A_j(t)\)。
初始化时 \(W[0]=1\)，其余都为 0。处理某个面额 \(c\) 时，对金额做升序更新：
$$W[t]\leftarrow W[t]+W[t-c]\qquad (t=c,c+1,\dots,200).$$
这里的“升序”不是细节，而是正确性的关键。更新前的 \(W[t]\) 仍然表示不使用当前面额时的方法数，即 \(A_{j-1}(t)\)。由于 \(t\) 从小到大扫描，\(W[t-c]\) 已经被当前面额更新过，所以它恰好等于 \(A_j(t-c)\)。两者相加后，\(W[t]\) 就变成了 \(A_j(t)\)。
如果改成降序扫描，就会阻止同一种面额被重复使用，那样得到的是另一类背包问题，而不是本题。升序扫描恰好实现了“每种硬币可无限次使用，但不同顺序不重复计数”。
三个实现都会先检查一个小型基准：凑出 10 便士的方法数应当是 \(11\)。这个例子非常适合说明递推在做什么。
先处理 1p 和 2p 时，凑出 10 的方法有 \(6\) 种，对应于使用 0、1、2、3、4、5 枚 2p。接着加入 5p 面额时，会把“凑出 5 的方法数”加到“凑出 10 的方法数”上，而前者等于 \(4\)，所以 10 的计数从 \(6\) 变成 \(10\)。最后再加入 10p 面额，会额外加上 \(W[0]=1\)，于是得到 \(11\)。
直接从组合上看，这 11 种情况也很清楚：一枚 10p；两枚 5p；一枚 5p 加上用 \(\{1,2\}\) 凑出 5 的 3 种方式；或者完全不用 5p，而只用 \(\{1,2\}\) 凑出 10 的 6 种方式。动态规划只是把这种分类讨论变成了统一的局部加法。
同一个计数问题也可以写成系数提取。每个面额 \(c\) 对应一个几何级数
$$1+x^c+x^{2c}+x^{3c}+\cdots=\frac{1}{1-x^c},$$
因为这种硬币可以选 0 枚、1 枚、2 枚、3 枚，等等。因此，所求答案就是下面乘积中 \(x^{200}\) 的系数：
$$\prod_{c\in C}\frac{1}{1-x^c} =\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})}.$$
程序中的动态规划，本质上就是按面额逐步构造这个乘积，并且只保留 200 次及以下的系数，因为更高次数对目标金额没有任何作用。
C++、Python 和 Java 三个实现都把八种英国硬币面额按升序存储，把目标金额默认设为 200，并分配一个长度为 201 的数组。金额 0 的位置初始化为 1，其余位置初始化为 0。
对于每一种硬币，程序都会从该面额开始一路扫描到目标金额，并把较小金额的计数加到当前金额上。处理完 1p 之后，每个金额都只有一种表示方式。之后每加入一种新面额，就把“至少使用一枚该面额”的表示方式整体补充进来。
在输出主结果之前，三个实现都会验证两个小检查点：5 便士应当有 4 种方法，10 便士应当有 11 种方法。这两个检查同时验证了递推关系和循环顺序。随后程序直接读取 200 便士对应的数组项并输出，得到的就是 \(73682\)。
如果有 \(m\) 种面额、目标金额为 \(T\)，那么该方法的时间复杂度是 \(O(mT)\)，空间复杂度是 \(O(T)\)。在本题中 \(m=8\)、\(T=200\)，所以数组只有 201 个位置。
再具体一点，内部的加法总共执行了
$$\sum_{c\in C}(200-c+1)=1220$$
次。这也是为什么三个实现都能在极短时间内完成 Problem 31。
В британской денежной системе используются восемь номиналов \(C=\{1,2,5,10,20,50,100,200\}\) пенсов. Нужно найти количество неупорядоченных наборов этих монет, сумма которых равна 200 пенсам, то есть £2.
Эквивалентно, требуется посчитать число неотрицательных целочисленных решений уравнения
$$n_1+2n_2+5n_5+10n_{10}+20n_{20}+50n_{50}+100n_{100}+200n_{200}=200.$$
Ключевое условие состоит в том, что порядок монет не важен. Имеет значение только количество монет каждого номинала. Реализации вычисляют это число точно, и окончательный результат равен \(73682\).
Удобнее всего рассматривать номиналы по возрастанию и после каждого шага хранить, сколько способов существует для каждой промежуточной суммы при использовании только уже разрешенных монет.
Обозначим отсортированные номиналы через \(c_1=1,c_2=2,\dots,c_8=200\). Пусть \(A_j(t)\) означает число способов получить \(t\) пенсов, используя только первые \(j\) номиналов. Тогда \(A_j(t)\) — это число ограниченных разбиений числа \(t\): части могут повторяться, но каждая часть должна принадлежать множеству \(\{c_1,\dots,c_j\}\).
Начальные условия таковы:
$$A_0(0)=1,\qquad A_0(t)=0\quad (t>0).$$
Без доступных номиналов сумму 0 можно получить ровно одним способом — пустым выбором, а любую положительную сумму получить нельзя.
Зафиксируем \(j\) и сумму \(t\). Любая комбинация, входящая в \(A_j(t)\), попадает ровно в один из двух классов.
Либо она не использует монету \(c_j\) вообще, и тогда вклад равен \(A_{j-1}(t)\). Либо использует хотя бы одну такую монету; если убрать одну монету \(c_j\), останется допустимая комбинация для суммы \(t-c_j\), которая по-прежнему может содержать монеты \(c_j\). Это дает вклад \(A_j(t-c_j)\).
Следовательно, при \(t\ge c_j\) имеем
$$A_j(t)=A_{j-1}(t)+A_j(t-c_j).$$
Если \(t<c_j\), то номинал \(c_j\) появиться не может, и потому \(A_j(t)=A_{j-1}(t)\). Именно эта рекуррентная формула лежит в основе решения.
Рекурсия использует только предыдущий набор номиналов и текущий набор на меньших суммах, поэтому двумерную таблицу можно свернуть в одномерный массив \(W[0],W[1],\dots,W[200]\). После завершения обработки номинала \(c_j\) будем понимать \(W[t]\) как \(A_j(t)\).
Изначально \(W[0]=1\), а все остальные ячейки равны 0. При обработке монеты \(c\) суммы обновляются в возрастающем порядке:
$$W[t]\leftarrow W[t]+W[t-c]\qquad (t=c,c+1,\dots,200).$$
Порядок возрастания здесь принципиален. До обновления \(W[t]\) еще хранит \(A_{j-1}(t)\). Поскольку \(t\) растет, элемент \(W[t-c]\) уже обновлен для текущего номинала и равен \(A_j(t-c)\). После сложения \(W[t]\) становится точным значением \(A_j(t)\).
Если бы обход шел по убыванию, одну и ту же монету нельзя было бы использовать повторно, то есть решалась бы другая задача. Возрастающий обход как раз и кодирует правило «каждый номинал можно брать неограниченно много раз, но порядок не учитывается».
Реализации проверяют как контрольный пример, что число способов получить 10 пенсов равно \(11\). Это наглядно демонстрирует действие рекурсии.
После обработки монет 1p и 2p существует \(6\) способов получить 10, что соответствует использованию 0, 1, 2, 3, 4 или 5 монет по 2p. При добавлении номинала 5p к числу способов для 10 прибавляется число способов получить 5, а это \(4\). Поэтому значение для 10 увеличивается с \(6\) до \(10\). Затем при обработке 10p добавляется еще \(W[0]=1\), и итог становится равен \(11\).
В явном разбиении это выглядит так: одна монета 10p; две монеты 5p; одна монета 5p плюс один из 3 способов получить 5 с помощью \(\{1,2\}\); или ни одной монеты 5p и один из 6 способов получить 10 с помощью \(\{1,2\}\). Динамическое программирование просто превращает такое разбиение случаев в последовательность локальных обновлений.
Тот же самый подсчет можно описать как задачу извлечения коэффициента. Каждый номинал \(c\) дает геометрический ряд
$$1+x^c+x^{2c}+x^{3c}+\cdots=\frac{1}{1-x^c},$$
потому что монет этого номинала можно взять 0, 1, 2, 3, ... штук. Поэтому искомое количество равно коэффициенту при \(x^{200}\) в произведении
$$\prod_{c\in C}\frac{1}{1-x^c} =\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})}.$$
Динамическая программа фактически и строит это произведение, отбрасывая коэффициенты степеней выше 200, потому что они не влияют на целевую сумму.
Реализации на C++, Python и Java хранят восемь британских номиналов в возрастающем порядке, по умолчанию берут цель 200 и создают массив длины 201. Ячейка для суммы 0 инициализируется значением 1, а все остальные — нулем.
Для каждой монеты программа проходит все суммы от ее значения до цели и добавляет количество способов для меньшей суммы. После прохода по 1p каждая сумма имеет ровно одно представление. Каждый следующий проход добавляет представления, содержащие хотя бы одну монету нового номинала.
Перед печатью основного ответа выполняются две маленькие проверки: 4 способа для 5 пенсов и 11 способов для 10 пенсов. Эти тесты подтверждают правильность и рекурсии, и порядка циклов. После этого выводится значение для суммы 200, а именно \(73682\).
Для \(m\) номиналов и цели \(T\) алгоритм работает за \(O(mT)\) и использует \(O(T)\) памяти. В нашей задаче \(m=8\) и \(T=200\), так что массив содержит всего 201 элемент.
Если считать точнее, то внутренняя операция сложения выполняется ровно
$$\sum_{c\in C}(200-c+1)=1220$$
раз. Поэтому все три реализации решают Problem 31 практически мгновенно.
في النظام النقدي البريطاني توجد ثماني فئات من العملات، وهي \(C=\{1,2,5,10,20,50,100,200\}\) بنسًا. المطلوب هو عدد المجموعات غير المرتبة من هذه العملات التي يكون مجموعها 200 بنس، أي £2.
وبصياغة مكافئة، نريد عدد الحلول الصحيحة غير السالبة للمعادلة
$$n_1+2n_2+5n_5+10n_{10}+20n_{20}+50n_{50}+100n_{100}+200n_{200}=200.$$
الشرط الحاسم هنا هو أن الترتيب لا يهم. المهم فقط هو عدد العملات المختارة من كل فئة. التطبيقات تحسب هذا العدد بدقة، والنتيجة النهائية هي \(73682\).
الطريقة الطبيعية هنا هي إدخال الفئات النقدية واحدة بعد أخرى، وفي كل مرحلة نحفظ عدد الطرق الممكنة لتكوين كل مبلغ وسيط باستخدام الفئات التي سُمح بها حتى تلك اللحظة فقط.
لنكتب الفئات المرتبة على الصورة \(c_1=1,c_2=2,\dots,c_8=200\). ولتكن \(A_j(t)\) هي عدد الطرق لتكوين \(t\) بنسًا باستخدام أول \(j\) فئات فقط. بهذا المعنى فإن \(A_j(t)\) يعد تقسيمات العدد \(t\) مع تكرار مسموح، لكن بشرط أن تكون الأجزاء مأخوذة من \(\{c_1,\dots,c_j\}\).
شروط البداية هي
$$A_0(0)=1,\qquad A_0(t)=0\quad (t>0).$$
فمن دون أي فئات متاحة توجد طريقة واحدة فقط لتكوين الصفر، وهي الاختيار الفارغ، ولا توجد أي طريقة لتكوين مبلغ موجب.
لنثبت \(j\) ومبلغًا \(t\). كل تركيب يدخل في \(A_j(t)\) يقع بالضبط في واحدة من حالتين.
إما أنه لا يستخدم الفئة \(c_j\) إطلاقًا، وعندها يساهم بمقدار \(A_{j-1}(t)\). أو أنه يستخدم على الأقل عملة واحدة من الفئة \(c_j\). وإذا حذفنا عملة واحدة من هذه الفئة، بقي تركيب صحيح للمبلغ \(t-c_j\) وما يزال مسموحًا له أن يستخدم \(c_j\) مرة أخرى. وهذا يعطي المساهمة \(A_j(t-c_j)\).
إذًا عندما يكون \(t\ge c_j\) نحصل على
$$A_j(t)=A_{j-1}(t)+A_j(t-c_j).$$
أما إذا كان \(t<c_j\)، فلا يمكن ظهور الفئة \(c_j\) أصلًا، وبالتالي \(A_j(t)=A_{j-1}(t)\). هذه هي العلاقة العودية الدقيقة التي يعتمد عليها الحل.
بما أن العلاقة لا تحتاج إلا إلى مجموعة الفئات السابقة وإلى المجموعة الحالية عند مبالغ أصغر، يمكن ضغط الجدول الثنائي إلى مصفوفة أحادية \(W[0],W[1],\dots,W[200]\). وبعد إنهاء معالجة الفئة \(c_j\)، نفسر \(W[t]\) على أنه \(A_j(t)\).
في البداية نضع \(W[0]=1\) وجميع الخانات الأخرى تساوي 0. وعند معالجة فئة \(c\) نحدّث المبالغ بترتيب تصاعدي:
$$W[t]\leftarrow W[t]+W[t-c]\qquad (t=c,c+1,\dots,200).$$
الترتيب التصاعدي هنا أساسي جدًا. قبل التحديث تكون \(W[t]\) ما تزال تمثل \(A_{j-1}(t)\). ولأن \(t\) يزداد تدريجيًا، فإن \(W[t-c]\) تكون قد حُدِّثت بالفعل للفئة الحالية، ولذلك فهي تساوي \(A_j(t-c)\). وبعد الجمع تصبح \(W[t]\) مساوية تمامًا لـ \(A_j(t)\).
ولو سُمح بالمرور التنازلي بدلًا من التصاعدي، لَمُنع استخدام الفئة نفسها أكثر من مرة، وعندها نصبح أمام مسألة مختلفة. المسح التصاعدي هو الذي يحقق بالضبط قاعدة “عدد غير محدود من كل عملة، لكن من دون عدّ الترتيبات المختلفة على أنها حلول مختلفة”.
التطبيقات تتحقق أولًا من قيمة صغيرة مرجعية، وهي أن عدد طرق تكوين 10 بنسات يساوي \(11\). هذا المثال الصغير يوضح آلية العودية بصورة ممتازة.
بعد معالجة 1p و2p فقط، يوجد \(6\) طرق لتكوين 10، وهي الموافقة لاستخدام 0 أو 1 أو 2 أو 3 أو 4 أو 5 عملات من فئة 2p. عند إدخال فئة 5p، نضيف عدد طرق تكوين 5، وهذا العدد يساوي \(4\)، فتنتقل قيمة 10 من \(6\) إلى \(10\). ثم عند معالجة 10p نضيف \(W[0]=1\)، فنحصل في النهاية على \(11\).
وبلغة العد المباشر، هذه الحالات الإحدى عشرة هي: عملة واحدة من 10p؛ عملتان من 5p؛ عملة 5p واحدة مع واحدة من الطرق الثلاث لتكوين 5 باستخدام \(\{1,2\}\)؛ أو من دون أي 5p مع واحدة من الطرق الست لتكوين 10 باستخدام \(\{1,2\}\). البرمجة الديناميكية تختصر هذا التفريع كله في تحديثات محلية بسيطة.
يمكن أيضًا وصف المسألة على أنها استخراج معامل. فكل فئة \(c\) تعطي السلسلة الهندسية
$$1+x^c+x^{2c}+x^{3c}+\cdots=\frac{1}{1-x^c},$$
لأننا نستطيع اختيار 0 أو 1 أو 2 أو 3 أو ... عملات من هذه الفئة. وعليه فإن العدد المطلوب هو معامل \(x^{200}\) في
$$\prod_{c\in C}\frac{1}{1-x^c} =\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})}.$$
البرنامج الديناميكي ليس إلا طريقة عملية لبناء هذا الضرب مع تجاهل جميع المعاملات التي تتجاوز الدرجة 200 لأنها لا تؤثر في المبلغ الهدف.
تخزن تطبيقات C++ وPython وJava الفئات البريطانية الثماني بترتيب تصاعدي، وتستخدم 200 هدفًا افتراضيًا، ثم تنشئ مصفوفة طولها 201. الخانة الخاصة بالمبلغ 0 تهيأ إلى 1، وجميع الخانات الأخرى تهيأ إلى 0.
لكل فئة نقدية، تمر الشيفرة على كل المبالغ من تلك الفئة حتى الهدف وتضيف عدد الطرق الخاص بالمبلغ الأصغر. بعد المرور على 1p يصبح لكل مبلغ تمثيل واحد بالضبط. وكل مرور لاحق يضيف التمثيلات التي تستخدم على الأقل عملة واحدة من الفئة الجديدة.
قبل طباعة النتيجة الأساسية، تنفذ الشيفرة تحققين صغيرين: 4 طرق لمبلغ 5 بنسات و11 طريقة لمبلغ 10 بنسات. هذان الاختباران يؤكدان صحة كل من العودية وترتيب الحلقات. بعد ذلك تُقرأ القيمة الخاصة بالمبلغ 200 مباشرة وتُطبع، وهي \(73682\).
إذا كان لدينا \(m\) فئات نقدية وهدف مقداره \(T\)، فإن الزمن هو \(O(mT)\) والمساحة هي \(O(T)\). في هذه المسألة \(m=8\) و\(T=200\)، لذلك لا نحتاج إلا إلى مصفوفة من 201 خانة.
وبشكل أدق، فإن عملية الجمع الداخلية تُنفَّذ تمامًا
$$\sum_{c\in C}(200-c+1)=1220$$
مرة. ولهذا تنهي التطبيقات الثلاثة Problem 31 بسرعة تكاد تكون فورية.