The problem asks for the number of shortest routes from the upper-left corner of a \(20\times 20\) grid to the lower-right corner when every move is restricted to one step right or one step down. Brute-force enumeration would mean generating every admissible route, but the geometry of the grid makes a closed-form count possible.
More generally, for an \(n\times n\) grid the question is to count monotone lattice paths from \((0,0)\) to \((n,n)\). In the Project Euler instance \(n=20\), so the target quantity is \(\binom{40}{20}\).
The key observation is that every shortest path has the same length and the same multiset of moves. Once a path is encoded as an ordering problem, the answer becomes a binomial coefficient, and the implementations can evaluate that coefficient exactly without ever forming huge factorials.
To go from \((0,0)\) to \((n,n)\), the horizontal coordinate must increase by \(n\) and the vertical coordinate must increase by \(n\). Since the only allowed moves are \(R=(1,0)\) and \(D=(0,1)\), any shortest path contains exactly \(n\) right moves and \(n\) down moves, so its total length is forced to be \(2n\).
There is therefore no choice in how many times each move appears. The only freedom is the order in which those \(2n\) moves are arranged.
Once the step counts are fixed, a path is completely determined by choosing which \(n\) of the \(2n\) positions are right moves. The remaining \(n\) positions must then be down moves. This gives a bijection between shortest lattice paths and \(n\)-element subsets of a \(2n\)-element set, so
$$L(n)=\binom{2n}{n}=\frac{(2n)!}{n!\,n!}.$$
For the Project Euler input,
$$L(20)=\binom{40}{20}=137846528820.$$
This number is the central binomial coefficient, which is exactly the combinatorial object the code evaluates.
If \(P(i,j)\) denotes the number of valid monotone paths from \((0,0)\) to \((i,j)\), then any such path reaching \((i,j)\) must come from either \((i-1,j)\) or \((i,j-1)\). Those two cases are disjoint, so for \(i,j\ge 1\),
$$P(i,j)=P(i-1,j)+P(i,j-1),$$
with boundary conditions
$$P(i,0)=1,\qquad P(0,j)=1.$$
This is Pascal's triangle written on the grid. The implementations do not use dynamic programming for the final answer, but this recurrence is the natural invariant behind the combinatorics and a useful way to verify the formula.
For \(n=2\), every shortest path is an ordering of the multiset \(\{R,R,D,D\}\). The six possibilities are \(RRDD\), \(RDRD\), \(RDDR\), \(DRRD\), \(DRDR\), and \(DDRR\), so
$$L(2)=\binom{4}{2}=6.$$
The recurrence viewpoint agrees: starting with ones along the top edge and left edge, the interior counts become \(2\), \(3\), and finally \(6\) in the lower-right corner. This small case is also used as a checkpoint in the implementations.
Computing \((2n)!\) and then dividing by \((n!)^2\) is mathematically correct but numerically clumsy, because the intermediate factorials grow much faster than the final answer. The C++ and Java implementations therefore evaluate a generic binomial coefficient by the product
$$\binom{N}{k}=\prod_{i=1}^{k}\frac{N-k+i}{i},$$
and then substitute \(N=2n\) and \(k=n\).
After the \(i\)-th update, the running value equals \(\binom{N-k+i}{i}\). That invariant explains why each division by \(i\) is exact: the algorithm never leaves the integers. The generic routine also replaces \(k\) by \(\min(k,N-k)\); in this square-grid problem that symmetry does not change the final loop length, but it is the correct combinatorial simplification in general.
The C++, Python, and Java implementations all reduce the problem to evaluating \(\binom{2n}{n}\). None of them enumerates paths, and none of them needs to store a two-dimensional grid. The C++ and Java versions perform the multiplicative update step by step, while the Python version calls the standard library's exact binomial routine.
The C++ implementation uses wider intermediate arithmetic during the multiply-then-divide loop and checks that the final value still fits into 64-bit storage before printing it. The Java implementation uses 64-bit signed integers, which are sufficient for the target case \(n=20\). The Python implementation relies on arbitrary-precision integers, so it can compute the same combinatorial quantity without overflow concerns. Small sanity checks such as \(L(1)=2\) and \(L(2)=6\) confirm that the formula has been encoded correctly.
The implemented method performs one multiplicative loop of length \(k\), where \(k=n\) for this problem. That gives \(O(n)\) arithmetic steps and \(O(1)\) extra space in the C++ and Java implementations. For \(n=20\), the calculation is effectively instantaneous.
For comparison, the lattice recurrence would require \(O(n^2)\) time and either \(O(n^2)\) space for a full table or \(O(n)\) space with row compression. The binomial route is superior here because the mathematics has already collapsed the search space to one exact closed form.
Gesucht ist die Anzahl der kürzesten Wege von der oberen linken zur unteren rechten Ecke eines \(20\times 20\)-Gitters, wenn jeder Schritt nur nach rechts oder nach unten gehen darf. Ein brutales Durchzählen aller Möglichkeiten wäre unnötig, weil die Gittergeometrie eine exakte kombinatorische Formel liefert.
Allgemeiner fragt das Problem für ein \(n\times n\)-Gitter nach der Zahl monotoner Gitterpfade von \((0,0)\) nach \((n,n)\). Im Euler-Fall ist \(n=20\), also ist die gesuchte Größe \(\binom{40}{20}\).
Der Kern der Lösung ist, einen Pfad nicht als Zeichnung im Gitter, sondern als geordnete Folge von Schritten zu betrachten. Sobald diese Kodierung klar ist, reduziert sich das gesamte Problem auf einen Binomialkoeffizienten, den die Implementierungen exakt und ohne große Fakultäten auswerten.
Um von \((0,0)\) nach \((n,n)\) zu gelangen, muss die \(x\)-Koordinate um \(n\) und die \(y\)-Koordinate ebenfalls um \(n\) erhöht werden. Da nur \(R=(1,0)\) und \(D=(0,1)\) erlaubt sind, enthält jeder kürzeste Weg genau \(n\) Rechtsschritte und \(n\) Abwärtsschritte. Die Länge ist also zwingend \(2n\).
Damit ist nicht die Anzahl der Schrittarten variabel, sondern nur ihre Reihenfolge innerhalb der gesamten Folge von \(2n\) Zügen.
Ist die Anzahl der Schritte festgelegt, dann ist ein Weg vollständig bestimmt, sobald man auswählt, welche \(n\) der \(2n\) Positionen mit \(R\) besetzt sind. Die übrigen Positionen müssen dann \(D\) sein. So erhält man eine Bijektion zwischen kürzesten Wegen und \(n\)-elementigen Teilmengen einer \(2n\)-elementigen Menge. Also gilt
$$L(n)=\binom{2n}{n}=\frac{(2n)!}{n!\,n!}.$$
Für den konkreten Euler-Fall folgt
$$L(20)=\binom{40}{20}=137846528820.$$
Diese Zahl ist der zentrale Binomialkoeffizient und genau das kombinatorische Objekt, das die Programme berechnen.
Bezeichne mit \(P(i,j)\) die Anzahl der monotonen Wege von \((0,0)\) nach \((i,j)\). Jeder Weg nach \((i,j)\) kommt entweder aus \((i-1,j)\) oder aus \((i,j-1)\); andere Vorgänger gibt es nicht. Daher gilt für \(i,j\ge 1\)
$$P(i,j)=P(i-1,j)+P(i,j-1),$$
mit Randwerten
$$P(i,0)=1,\qquad P(0,j)=1.$$
Das ist Pascalsches Dreieck auf dem Gitter. Die Implementierungen verwenden diese dynamische Programmierung nicht direkt, aber die Rekurrenz ist der natürliche Invariant hinter der Formel und eine gute Plausibilitätskontrolle.
Für \(n=2\) ist jeder kürzeste Weg eine Anordnung des Multimengensymbols \(\{R,R,D,D\}\). Die sechs Möglichkeiten sind \(RRDD\), \(RDRD\), \(RDDR\), \(DRRD\), \(DRDR\) und \(DDRR\). Also
$$L(2)=\binom{4}{2}=6.$$
Auch die Rekurrenz ergibt denselben Wert: Mit Einsen am oberen Rand und linken Rand entstehen im Inneren die Werte \(2\), \(3\) und schließlich \(6\) in der rechten unteren Ecke. Dieser kleine Fall dient zugleich als Kontrollbeispiel im Code.
Die Darstellung \(\frac{(2n)!}{(n!)^2}\) ist mathematisch korrekt, aber numerisch ungünstig, weil die Zwischenwerte der Fakultäten viel schneller wachsen als das Endergebnis. Deshalb berechnen die C++- und Java-Implementierungen einen allgemeinen Binomialkoeffizienten über
$$\binom{N}{k}=\prod_{i=1}^{k}\frac{N-k+i}{i},$$
und setzen danach \(N=2n\) und \(k=n\) ein.
Nach dem \(i\)-ten Schritt ist der laufende Wert gleich \(\binom{N-k+i}{i}\). Genau dieser Invariant erklärt, warum jede Division durch \(i\) ohne Rest aufgeht: Die Rechnung bleibt vollständig im Ganzzahlbereich. Zusätzlich ersetzt die allgemeine Routine \(k\) durch \(\min(k,N-k)\); im quadratischen Spezialfall ändert das nichts, ist aber die richtige Symmetrievereinfachung für Binomialkoeffizienten.
Die C++-, Python- und Java-Implementierungen reduzieren das Problem alle auf die Auswertung von \(\binom{2n}{n}\). Es werden weder Pfade explizit erzeugt noch zweidimensionale Tabellen für die Hauptrechnung gespeichert. C++ und Java führen die Produktaktualisierung Schritt für Schritt aus, während Python dieselbe exakte Kombinatorik der Standardbibliothek überlässt.
Die C++-Implementierung verwendet breitere Zwischenarithmetik im Multiplikations-und-Divisions-Zyklus und prüft anschließend, ob das Endergebnis noch in 64 Bit passt. Die Java-Implementierung verwendet vorzeichenbehaftete 64-Bit-Ganzzahlen, was für den Zielwert bei \(n=20\) ausreicht. Python arbeitet mit beliebig großen Ganzzahlen und hat daher kein Überlaufproblem bei derselben Formel. Kleine Prüfwerte wie \(L(1)=2\) und \(L(2)=6\) dienen als schnelle Konsistenztests.
Die implementierte Methode benötigt genau eine Schleife der Länge \(k\), wobei hier \(k=n\) ist. Damit ergibt sich \(O(n)\) Zeit und \(O(1)\) zusätzlicher Speicher in den C++- und Java-Versionen. Für \(n=20\) ist die Rechnung praktisch sofort abgeschlossen.
Zum Vergleich: Die Gitterrekurrenz hätte \(O(n^2)\) Zeitbedarf und \(O(n^2)\) Speicher bei voller Tabelle beziehungsweise \(O(n)\) Speicher mit Zeilenkompression. Der Binomialansatz ist hier klar überlegen, weil die Mathematik den gesamten Suchraum bereits zu einer geschlossenen Formel verdichtet hat.
Problem, yalnızca sağa ve aşağı hareketlere izin verildiğinde \(20\times 20\) bir ızgaranın sol üst köşesinden sağ alt köşesine giden en kısa yolların kaç tane olduğunu sorar. Tüm yolları tek tek üretmek gereksizdir; çünkü ızgara yapısı sayımı doğrudan bir kombinatorik formüle indirir.
Daha genel olarak soru, \(n\times n\) bir ızgarada \((0,0)\) noktasından \((n,n)\) noktasına giden monoton kafes yollarını saymaktır. Project Euler örneğinde \(n=20\) olduğundan hedef büyüklük \(\binom{40}{20}\) olur.
Temel fikir, yolu bir geometri nesnesi olarak değil, sıralanmış bir hamle dizisi olarak kodlamaktır. Bu kodlama kurulduğu anda problem bir binom katsayısına çöker ve uygulamalar da bu katsayıyı büyük faktöriyel değerleri oluşturmadan tam olarak hesaplar.
\((0,0)\)'dan \((n,n)\)'ye gitmek için yatay koordinatın \(n\), düşey koordinatın da \(n\) kadar artması gerekir. İzin verilen tek hamleler \(R=(1,0)\) ve \(D=(0,1)\) olduğundan, her en kısa yol tam olarak \(n\) sağ ve \(n\) aşağı hamlesi içerir. Dolayısıyla toplam adım sayısı zorunlu olarak \(2n\)'dir.
Yani serbest olan şey hamle sayıları değil, bu \(2n\) hamlenin hangi sırayla dizileceğidir.
Hamle sayıları sabitlendikten sonra, bir yol tamamen şu seçimle belirlenir: \(2n\) adım konumundan hangileri sağ hamlesi olacak? Bu konumlardan \(n\) tanesini seçmek yeterlidir; geri kalanlar otomatik olarak aşağı hamlesidir. Böylece en kısa yollar ile \(2n\) elemanlı bir kümenin \(n\) elemanlı altkümeleri arasında birebir eşleme kurulur. Sonuç:
$$L(n)=\binom{2n}{n}=\frac{(2n)!}{n!\,n!}.$$
Project Euler girdisi için
$$L(20)=\binom{40}{20}=137846528820.$$
elde edilir. Bu sayı merkezi binom katsayısıdır ve kodun doğrudan hesapladığı nesne de tam olarak budur.
\(P(i,j)\), \((0,0)\)'dan \((i,j)\)'ye giden geçerli monoton yol sayısı olsun. \((i,j)\)'ye ulaşan her yol, son adımında ya \((i-1,j)\)'den ya da \((i,j-1)\)'den gelir. Bu iki durum ayrık olduğundan \(i,j\ge 1\) için
$$P(i,j)=P(i-1,j)+P(i,j-1),$$
ve sınır koşulları
$$P(i,0)=1,\qquad P(0,j)=1$$
şeklindedir. Bu, Pascal üçgeninin ızgara üzerinde yazılmış halidir. Uygulamalar son cevabı bu yöntemle üretmez; ancak bu bağıntı formülün arkasındaki doğal değişmezi verir ve sonucu denetlemek için çok yararlıdır.
\(n=2\) için her en kısa yol, \(\{R,R,D,D\}\) çoklu kümesinin bir sıralamasıdır. Altı olasılık \(RRDD\), \(RDRD\), \(RDDR\), \(DRRD\), \(DRDR\) ve \(DDRR\) olduğundan
$$L(2)=\binom{4}{2}=6$$
olur. Yineleme de aynı sonucu verir: üst kenar ve sol kenar boyunca birler yazıldığında iç bölgedeki sayılar \(2\), \(3\) ve sağ alt köşede \(6\) olur. Bu küçük durum, uygulamalardaki kontrol örneklerinden biridir.
\(\frac{(2n)!}{(n!)^2}\) ifadesi matematiksel olarak doğru olsa da sayısal açıdan kaba bir yöntemdir; çünkü ara faktöriyel değerleri son cevaptan çok daha hızlı büyür. Bu yüzden C++ ve Java uygulamaları genel bir binom katsayısını şu çarpımla hesaplar:
$$\binom{N}{k}=\prod_{i=1}^{k}\frac{N-k+i}{i},$$
ardından bu problem için \(N=2n\) ve \(k=n\) yerleştirilir.
\(i\). güncellemeden sonra çalışan değer \(\binom{N-k+i}{i}\)'ye eşittir. İşte bu değişmez, her adımda \(i\) ile bölümün neden tam bölündüğünü açıklar: algoritma hiçbir anda tamsayılar kümesinin dışına çıkmaz. Genel binom yordamı ayrıca \(k\) değerini \(\min(k,N-k)\) ile değiştirir; kare ızgara durumunda bu uzunluğu değiştirmese de genel simetriyi doğru şekilde kullanır.
C++, Python ve Java uygulamalarının üçü de problemi \(\binom{2n}{n}\) hesaplamasına indirger. Hiçbiri yolları tek tek saymaz ve ana hesaplama için iki boyutlu bir tablo tutmaz. C++ ve Java sürümleri çarp-böl güncellemesini adım adım uygular; Python sürümü ise aynı kesin kombinatorik hesabı standart kütüphanedeki binom yordamına bırakır.
C++ uygulaması, çarpma-bölme döngüsünde daha geniş ara aritmetik kullanır ve çıktıdan önce sonucun 64 bitlik depolamaya sığdığını doğrular. Java uygulaması, hedef durum \(n=20\) için yeterli olan işaretli 64 bit tamsayılarla çalışır. Python uygulaması keyfi duyarlıklı tamsayılara yaslandığı için aynı kombinatorik miktarı taşma endişesi olmadan hesaplar. \(L(1)=2\) ve \(L(2)=6\) gibi küçük testler de formülün doğru kurulduğunu teyit eder.
Uygulanan yöntem, uzunluğu \(k\) olan tek bir çarpımsal döngü çalıştırır; bu problemde \(k=n\)'dir. Böylece C++ ve Java sürümlerinde \(O(n)\) aritmetik adım ve \(O(1)\) ek bellek elde edilir. \(n=20\) için çalışma süresi pratikte anlıktır.
Karşılaştırma için, ızgara yinelemesi tam tabloyla \(O(n^2)\) zaman ve \(O(n^2)\) bellek, satır sıkıştırmasıyla \(O(n)\) bellek gerektirirdi. Burada binom yaklaşımı daha güçlüdür; çünkü matematik arama uzayını zaten tek bir kapalı ifadeye indirgemiştir.
La pregunta es cuántas rutas más cortas existen desde la esquina superior izquierda hasta la esquina inferior derecha de una cuadrícula \(20\times 20\) si cada movimiento permitido es solo un paso a la derecha o un paso hacia abajo. Enumerar todos los caminos sería innecesario, porque la estructura del problema conduce a una cuenta combinatoria exacta.
En general, para una cuadrícula \(n\times n\), se trata de contar caminos reticulares monótonos desde \((0,0)\) hasta \((n,n)\). En la instancia de Project Euler se toma \(n=20\), de modo que la cantidad buscada es \(\binom{40}{20}\).
La idea central es dejar de pensar en el camino como un dibujo sobre la cuadrícula y verlo como una secuencia ordenada de movimientos. Una vez hecha esa codificación, todo el problema se reduce a un coeficiente binomial, y las implementaciones lo evalúan de forma exacta sin construir factoriales gigantes.
Para ir de \((0,0)\) a \((n,n)\), la coordenada horizontal debe aumentar en \(n\) y la vertical también debe aumentar en \(n\). Como las únicas jugadas permitidas son \(R=(1,0)\) y \(D=(0,1)\), cualquier camino mínimo contiene exactamente \(n\) movimientos a la derecha y \(n\) hacia abajo. Por lo tanto, su longitud total está forzada a ser \(2n\).
No hay libertad en cuántas veces aparece cada tipo de movimiento; la única libertad está en el orden de esos \(2n\) pasos.
Fijadas las cantidades, un camino queda completamente determinado al escoger cuáles \(n\) de las \(2n\) posiciones corresponden a movimientos a la derecha. Las posiciones restantes serán necesariamente movimientos hacia abajo. Esto produce una biyección entre caminos mínimos y subconjuntos de tamaño \(n\) de un conjunto de tamaño \(2n\). Así,
$$L(n)=\binom{2n}{n}=\frac{(2n)!}{n!\,n!}.$$
Para la entrada concreta de Project Euler,
$$L(20)=\binom{40}{20}=137846528820.$$
Ese número es el coeficiente binomial central, que es precisamente el objeto combinatorio calculado por el código.
Sea \(P(i,j)\) el número de caminos monótonos válidos desde \((0,0)\) hasta \((i,j)\). Todo camino que llega a \((i,j)\) debe venir en su último paso desde \((i-1,j)\) o desde \((i,j-1)\). Como ambos casos son disjuntos, para \(i,j\ge 1\) se cumple
$$P(i,j)=P(i-1,j)+P(i,j-1),$$
con condiciones de borde
$$P(i,0)=1,\qquad P(0,j)=1.$$
Esto no es otra cosa que el triángulo de Pascal escrito sobre la cuadrícula. Las implementaciones no usan esta programación dinámica para el cálculo final, pero la recurrencia expresa el invariante natural del problema y sirve para verificar la fórmula cerrada.
Cuando \(n=2\), cada camino mínimo es un ordenamiento del multiconjunto \(\{R,R,D,D\}\). Las seis posibilidades son \(RRDD\), \(RDRD\), \(RDDR\), \(DRRD\), \(DRDR\) y \(DDRR\). Por tanto,
$$L(2)=\binom{4}{2}=6.$$
La recurrencia da el mismo resultado: colocando unos en el borde superior y en el borde izquierdo, los valores interiores pasan a ser \(2\), \(3\) y finalmente \(6\) en la esquina inferior derecha. Este caso pequeño también aparece como comprobación en las implementaciones.
La expresión \(\frac{(2n)!}{(n!)^2}\) es correcta, pero numéricamente poco elegante, porque los factoriales intermedios crecen mucho más rápido que la respuesta final. Por eso las implementaciones en C++ y Java evalúan un coeficiente binomial general mediante
$$\binom{N}{k}=\prod_{i=1}^{k}\frac{N-k+i}{i},$$
y después sustituyen \(N=2n\) y \(k=n\).
Tras la \(i\)-ésima actualización, el valor acumulado es \(\binom{N-k+i}{i}\). Ese invariante explica por qué cada división por \(i\) es exacta: el algoritmo nunca sale del dominio de los enteros. La rutina general también reemplaza \(k\) por \(\min(k,N-k)\); en esta cuadrícula cuadrada no cambia el recorrido, pero sí expresa la simetría correcta del coeficiente binomial.
Las implementaciones en C++, Python y Java reducen el problema a evaluar \(\binom{2n}{n}\). Ninguna enumera caminos explícitamente ni necesita almacenar una tabla bidimensional para la parte principal. Las versiones de C++ y Java hacen la actualización multiplicativa paso a paso, mientras que la versión de Python delega la misma cuenta exacta a la rutina combinatoria de la biblioteca estándar.
La implementación en C++ usa aritmética intermedia más amplia durante el ciclo de multiplicar y dividir, y luego comprueba que el resultado final sigue cabiendo en 64 bits. La implementación en Java usa enteros con signo de 64 bits, suficientes para el caso objetivo \(n=20\). La implementación en Python se apoya en enteros de precisión arbitraria, así que puede calcular la misma cantidad sin preocuparse por desbordamientos. Valores pequeños como \(L(1)=2\) y \(L(2)=6\) sirven como pruebas rápidas de consistencia.
El método implementado realiza un único bucle multiplicativo de longitud \(k\), y en este problema \(k=n\). Eso produce \(O(n)\) pasos aritméticos y \(O(1)\) espacio extra en las versiones de C++ y Java. Para \(n=20\), el tiempo de ejecución es esencialmente instantáneo.
Como comparación, la recurrencia sobre la cuadrícula requeriría \(O(n^2)\) tiempo y \(O(n^2)\) memoria si se almacena la tabla completa, u \(O(n)\) memoria con compresión por filas. Aquí la vía binomial es superior porque la matemática ya comprimió todo el espacio de búsqueda en una sola fórmula cerrada.
这道题要求计算：在一个 \(20\times 20\) 的网格中，只允许向右走一步或向下走一步，从左上角走到右下角的最短路径一共有多少条。若直接枚举所有合法路径，思路虽然直观，但完全没有必要，因为这个问题本身具有非常清晰的组合结构。
更一般地说，对于一个 \(n\times n\) 的方格，问题是在 \((0,0)\) 到 \((n,n)\) 之间统计所有单调格路径的数量。Project Euler 的这一题取 \(n=20\)，因此核心就是求 \(\binom{40}{20}\)。
最关键的观察是：最短路径的总步数并不变化，变化的只是这些步如何排列。只要把一条路径改写成“步序列”的计数问题，整个题目就会直接化成一个二项式系数，而实现中也正是围绕这个系数进行精确计算。
从 \((0,0)\) 走到 \((n,n)\)，横坐标必须增加 \(n\)，纵坐标也必须增加 \(n\)。由于允许的步只有 \(R=(1,0)\) 和 \(D=(0,1)\)，所以任何一条最短路径都必须恰好包含 \(n\) 次向右和 \(n\) 次向下。于是总步数被固定为 \(2n\)。
换句话说，问题中没有“要走多少次右、多少次下”的自由度，唯一的自由度只是这 \(2n\) 步出现的顺序。
既然右步和下步的数量都已经固定，一条路径就完全由下面这个选择决定：在 \(2n\) 个位置中，哪 \(n\) 个位置放“向右”这一步。剩下的位置自然都是“向下”。因此，最短路径与一个 \(2n\) 元集合的 \(n\) 元子集之间存在双射，于是有
$$L(n)=\binom{2n}{n}=\frac{(2n)!}{n!\,n!}.$$
代入本题的 \(n=20\)，得到
$$L(20)=\binom{40}{20}=137846528820.$$
这个数就是中心二项式系数，也是三份实现真正计算的数学对象。
如果记 \(P(i,j)\) 为从 \((0,0)\) 到 \((i,j)\) 的合法单调路径条数，那么任何一条到达 \((i,j)\) 的路径，最后一步只能来自 \((i-1,j)\) 或 \((i,j-1)\)。这两个来源互不重叠，因此当 \(i,j\ge 1\) 时有
$$P(i,j)=P(i-1,j)+P(i,j-1),$$
边界条件为
$$P(i,0)=1,\qquad P(0,j)=1.$$
这其实就是把 Pascal 三角形写到了格点上。实现本身并不是靠动态规划给出最终答案，但这个递推很好地揭示了问题的不变量，也能用来验证组合公式没有出错。
当 \(n=2\) 时，每条最短路径都对应于多重集合 \(\{R,R,D,D\}\) 的一个排列。所有可能性共有六种：\(RRDD\)、\(RDRD\)、\(RDDR\)、\(DRRD\)、\(DRDR\)、\(DDRR\)。因此
$$L(2)=\binom{4}{2}=6.$$
若从递推角度看，沿着顶边和左边都填上 \(1\)，内部格点就依次得到 \(2\)、\(3\)，最后右下角得到 \(6\)。这也是实现中使用的小规模校验值之一，因此它不仅是教学例子，也是代码正确性的直接证据。
虽然 \(\frac{(2n)!}{(n!)^2}\) 是最直接的写法，但在数值实现上并不理想，因为 \((2n)!\) 与 \(n!\) 都会比最终答案大得多。C++ 和 Java 实现因此采用更稳健的乘法式：
$$\binom{N}{k}=\prod_{i=1}^{k}\frac{N-k+i}{i},$$
然后在本题中代入 \(N=2n\)、\(k=n\)。
这个写法的关键不变量是：做完第 \(i\) 次更新后，当前值恰好等于 \(\binom{N-k+i}{i}\)。因此每一步“先乘后除”中的除法都是整除，不会引入舍入误差，整个过程始终停留在整数范围内。通用二项式例程还会先把 \(k\) 替换成 \(\min(k,N-k)\)；对本题这种正方形网格，二者相等，所以循环次数不变，但这个对称化步骤在一般情况下是正确且有益的。
C++、Python 和 Java 三种实现都把问题归结为求 \(\binom{2n}{n}\)。它们都没有去枚举路径，也没有在主算法中构造一个二维路径表。C++ 与 Java 版本显式执行乘法式更新；Python 版本则把同样的精确组合计算交给标准库中的二项式函数完成。
C++ 实现会在乘除循环中使用更宽的中间整数类型，并在输出前确认最终结果仍然落在 64 位范围内。Java 实现采用 64 位有符号整数，而对于目标输入 \(n=20\) 这已经足够。Python 依赖任意精度整数，因此不会遇到同类的溢出问题。实现中还会用 \(L(1)=2\) 与 \(L(2)=6\) 这样的简单案例做快速自检，确认组合公式被正确编码。
实际采用的方法只需要一个长度为 \(k\) 的乘法循环，而在本题中 \(k=n\)。因此，C++ 与 Java 的实现都只需要 \(O(n)\) 次算术更新和 \(O(1)\) 的额外空间。对 \(n=20\) 这样的输入来说，运行时间几乎可以忽略。
作为对比，如果完全按网格递推来做，那么时间复杂度会是 \(O(n^2)\)，空间复杂度在完整表格下是 \(O(n^2)\)，做滚动压缩后也要 \(O(n)\)。本题之所以适合直接用二项式系数，是因为数学上已经把原本巨大的路径集合压缩成了一个封闭表达式。
Нужно посчитать число кратчайших путей из верхнего левого угла в нижний правый угол сетки \(20\times 20\), если разрешены только шаги вправо и вниз. Перебирать все маршруты по одному не нужно: у задачи есть простая и точная комбинаторная структура.
В более общем виде для сетки \(n\times n\) требуется число монотонных решетчатых путей из \((0,0)\) в \((n,n)\). В экземпляре Project Euler берется \(n=20\), поэтому центральной величиной становится \(\binom{40}{20}\).
Главная идея состоит в том, чтобы смотреть на путь не как на геометрическую линию на сетке, а как на упорядоченную последовательность шагов. После такой перекодировки задача сразу превращается в вычисление биномиального коэффициента, а реализации считают его точно, не строя огромные факториалы.
Чтобы перейти из \((0,0)\) в \((n,n)\), нужно увеличить горизонтальную координату на \(n\) и вертикальную координату тоже на \(n\). Поскольку допустимы только шаги \(R=(1,0)\) и \(D=(0,1)\), любой кратчайший путь обязан содержать ровно \(n\) шагов вправо и \(n\) шагов вниз. Значит, его длина всегда равна \(2n\).
Следовательно, выбор заключается не в количестве шагов каждого типа, а только в том, в каком порядке эти \(2n\) шагов расположены.
Когда количества шагов зафиксированы, путь полностью определяется выбором позиций, на которых стоят шаги вправо. Нужно выбрать \(n\) позиций из \(2n\), а все остальные автоматически становятся шагами вниз. Тем самым кратчайшие пути находятся во взаимно однозначном соответствии с \(n\)-элементными подмножествами \(2n\)-элементного множества. Поэтому
$$L(n)=\binom{2n}{n}=\frac{(2n)!}{n!\,n!}.$$
Для исходного значения \(n=20\) получаем
$$L(20)=\binom{40}{20}=137846528820.$$
Это центральный биномиальный коэффициент, и именно его в итоге вычисляют все три реализации.
Обозначим через \(P(i,j)\) количество корректных монотонных путей из \((0,0)\) в \((i,j)\). Любой путь, заканчивающийся в \((i,j)\), приходит туда либо из \((i-1,j)\), либо из \((i,j-1)\). Эти два случая не пересекаются, поэтому для \(i,j\ge 1\)
$$P(i,j)=P(i-1,j)+P(i,j-1),$$
при граничных условиях
$$P(i,0)=1,\qquad P(0,j)=1.$$
Это треугольник Паскаля, перенесенный на вершины сетки. Реализации не используют динамическое программирование для окончательного вычисления, но эта рекуррентность выражает естественный инвариант задачи и хорошо проверяет правильность закрытой формулы.
При \(n=2\) каждый кратчайший маршрут является перестановкой мультимножества \(\{R,R,D,D\}\). Возможны шесть строк: \(RRDD\), \(RDRD\), \(RDDR\), \(DRRD\), \(DRDR\) и \(DDRR\). Значит,
$$L(2)=\binom{4}{2}=6.$$
Рекуррентная схема дает тот же ответ: если поставить единицы вдоль верхней границы и левой границы, внутри возникают значения \(2\), \(3\), а затем \(6\) в правом нижнем углу. Этот небольшой пример используется и как практическая проверка корректности.
Запись \(\frac{(2n)!}{(n!)^2}\) корректна, но численно неудобна, потому что промежуточные факториалы растут намного быстрее конечного ответа. Поэтому реализации на C++ и Java вычисляют общий биномиальный коэффициент по формуле
$$\binom{N}{k}=\prod_{i=1}^{k}\frac{N-k+i}{i},$$
после чего подставляют \(N=2n\) и \(k=n\).
После \(i\)-го шага текущее значение равно \(\binom{N-k+i}{i}\). Этот инвариант сразу объясняет, почему деление на \(i\) на каждом шаге является точным: вычисление все время остается в целых числах. Общая процедура также заменяет \(k\) на \(\min(k,N-k)\); для квадратной сетки это ничего не меняет, но в общем случае правильно использует симметрию биномиального коэффициента.
Реализации на C++, Python и Java сводят задачу к вычислению \(\binom{2n}{n}\). Они не перечисляют пути явно и не строят двумерную таблицу как основную структуру данных. Версии на C++ и Java выполняют мультипликативное обновление шаг за шагом, а версия на Python передает ту же точную комбинаторную операцию стандартной библиотеке.
Реализация на C++ использует более широкий целочисленный тип для промежуточной арифметики в цикле умножения и деления, а затем проверяет, что итог по-прежнему помещается в 64 бита. Реализация на Java использует 64-битные знаковые целые числа, чего достаточно для целевого случая \(n=20\). Python опирается на длинную арифметику и поэтому не имеет аналогичных проблем с переполнением. Небольшие контрольные значения вроде \(L(1)=2\) и \(L(2)=6\) служат быстрыми проверками корректности.
Используемый метод содержит один мультипликативный цикл длины \(k\), а в этой задаче \(k=n\). Следовательно, реализации на C++ и Java выполняют \(O(n)\) арифметических действий и используют \(O(1)\) дополнительной памяти. Для \(n=20\) время работы практически мгновенно.
Для сравнения, рекуррентный подход на сетке потребовал бы \(O(n^2)\) времени и \(O(n^2)\) памяти при полной таблице либо \(O(n)\) памяти при сжатии по строкам. Здесь биномиальная формула выигрывает, потому что математика уже свернула огромный перебор в одно точное замкнутое выражение.
المطلوب هو حساب عدد المسارات الأقصر من الزاوية العلوية اليسرى إلى الزاوية السفلية اليمنى في شبكة \(20\times 20\)، مع السماح فقط بخطوة واحدة إلى اليمين أو خطوة واحدة إلى الأسفل. العد المباشر لكل المسارات ممكن من حيث التعريف لكنه غير عملي وغير ضروري، لأن بنية المسألة نفسها تقود إلى صيغة توافقية دقيقة.
وبصورة أعم، إذا كانت الشبكة \(n\times n\)، فنحن نعد المسارات الشبكية الأحادية الاتجاه من \((0,0)\) إلى \((n,n)\). في حالة Project Euler لدينا \(n=20\)، ولذلك فإن الكمية المركزية هي \(\binom{40}{20}\).
الفكرة الحاسمة هي أن ننظر إلى المسار بوصفه ترتيباً للخطوات لا رسماً داخل الشبكة. ما إن تُصاغ المسألة بهذه الطريقة حتى تنهار إلى معامل ثنائي واحد، وتقوم التطبيقات بحساب هذا المعامل بدقة من غير أن تبني عامليات ضخمة في الوسط.
للانتقال من \((0,0)\) إلى \((n,n)\) يجب أن يزداد الإحداثي الأفقي بمقدار \(n\) وأن يزداد الإحداثي الرأسي أيضاً بمقدار \(n\). وبما أن الخطوتين المسموح بهما فقط هما \(R=(1,0)\) و\(D=(0,1)\)، فإن كل مسار أقصر يحتوي بالضرورة على \(n\) خطوة إلى اليمين و\(n\) خطوة إلى الأسفل. إذن طول أي مسار أقصر ثابت ويساوي \(2n\).
هذا يعني أن الحرية ليست في عدد مرات ظهور كل نوع من الخطوات، بل في ترتيب هذه الخطوات فقط.
بعد تثبيت عدد الخطوات، يصبح المسار محدداً تماماً بمجرد اختيار أي \(n\) مواضع من أصل \(2n\) ستُخصص لخطوات اليمين. أما المواضع الباقية فستكون بالضرورة خطوات نزول. وهكذا نحصل على تقابل واحد لواحد بين المسارات الأقصر وبين المجموعات الجزئية ذات \(n\) عنصراً من مجموعة ذات \(2n\) عنصراً. لذلك
$$L(n)=\binom{2n}{n}=\frac{(2n)!}{n!\,n!}.$$
وبالتعويض عن \(n=20\) نحصل على
$$L(20)=\binom{40}{20}=137846528820.$$
وهذا هو المعامل الثنائي المركزي، وهو بالضبط الكائن التوافقي الذي تحسبه الشيفرات الثلاث.
إذا رمزنا بـ \(P(i,j)\) إلى عدد المسارات الأحادية الاتجاه من \((0,0)\) إلى \((i,j)\)، فإن أي مسار يصل إلى \((i,j)\) لا بد أن تأتي خطوته الأخيرة من \((i-1,j)\) أو من \((i,j-1)\). وهاتان الحالتان منفصلتان، لذا عندما يكون \(i,j\ge 1\) نحصل على
$$P(i,j)=P(i-1,j)+P(i,j-1),$$
مع الشروط الحدية
$$P(i,0)=1,\qquad P(0,j)=1.$$
وهذا ليس إلا مثلث باسكال مكتوباً على الشبكة. التطبيقات لا تستخدم البرمجة الديناميكية لاستخراج الجواب النهائي، لكن هذه العودية تكشف الثابت الطبيعي في المسألة وتوفر فحصاً رياضياً ممتازاً للصيغة المغلقة.
عندما يكون \(n=2\)، فإن كل مسار أقصر هو ترتيب ما للعناصر \(\{R,R,D,D\}\). الاحتمالات الستة هي \(RRDD\) و\(RDRD\) و\(RDDR\) و\(DRRD\) و\(DRDR\) و\(DDRR\). ومن ثم
$$L(2)=\binom{4}{2}=6.$$
والعودية تعطي الرقم نفسه أيضاً: إذا وضعنا الواحدات على الحافة العليا والحافة اليسرى، فإن القيم الداخلية تصبح \(2\) ثم \(3\) ثم \(6\) في الزاوية السفلية اليمنى. وهذا المثال الصغير يُستعمل كذلك كاختبار سلامة في التنفيذ.
الكتابة \(\frac{(2n)!}{(n!)^2}\) صحيحة رياضياً، لكنها ليست مريحة عددياً، لأن العامليات الوسيطة تنمو أسرع بكثير من الجواب النهائي. لهذا السبب تحسب تطبيقات C++ وJava المعامل الثنائي العام بواسطة
$$\binom{N}{k}=\prod_{i=1}^{k}\frac{N-k+i}{i},$$
ثم تضع \(N=2n\) و\(k=n\) في هذه المسألة.
بعد التحديث رقم \(i\) تصبح القيمة الجارية مساوية لـ \(\binom{N-k+i}{i}\). هذا الثابت يفسر لماذا تكون القسمة على \(i\) في كل خطوة قسمة تامة: الخوارزمية تبقى داخل الأعداد الصحيحة طوال الوقت. كما أن الروتين العام يستبدل \(k\) بـ \(\min(k,N-k)\)؛ وفي حالة الشبكة المربعة لا يغيّر ذلك شيئاً، لكنه يستفيد من التناظر الصحيح لمعاملات ثنائية الحدين في الحالة العامة.
تختزل تطبيقات C++ وPython وJava جميعها المسألة إلى حساب \(\binom{2n}{n}\). فلا توجد محاولة لتعداد المسارات واحداً واحداً، ولا توجد حاجة إلى تخزين جدول ثنائي الأبعاد في الخوارزمية الأساسية. نسختا C++ وJava تنفذان التحديث الضربي خطوة خطوة، أما نسخة Python فتفوّض العملية نفسها إلى روتين ثنائي الحدين الدقيق في المكتبة القياسية.
تستخدم نسخة C++ نوعاً أوسع للحسابات الوسيطة داخل حلقة الضرب ثم القسمة، ثم تتحقق من أن النتيجة النهائية ما زالت ضمن سعة 64-بت قبل الطباعة. وتستخدم نسخة Java أعداداً صحيحة موقعة من 64-بت، وهي كافية تماماً للحالة المستهدفة \(n=20\). أما Python فتعتمد على الأعداد الصحيحة ذات الدقة الاعتباطية، ولذلك لا تواجه المشكلة نفسها مع الفيض. كما تُستعمل قيم صغيرة مثل \(L(1)=2\) و\(L(2)=6\) بوصفها اختبارات سريعة لصحة الترميز.
الطريقة المنفذة تحتاج إلى حلقة ضرب واحدة طولها \(k\)، وفي هذه المسألة يكون \(k=n\). لذلك فإن نسختي C++ وJava تنفذان \(O(n)\) من الخطوات الحسابية وتستخدمان \(O(1)\) من الذاكرة الإضافية. وعندما يكون \(n=20\)، فإن زمن التنفيذ يكاد لا يُذكر.
وللمقارنة، فإن العمل بالعودية الشبكية يحتاج إلى \(O(n^2)\) زمناً، وإلى \(O(n^2)\) ذاكرة إذا خُزنت المصفوفة كاملة، أو \(O(n)\) ذاكرة مع ضغط الصفوف. في هذه المسألة يبقى المسار القائم على المعامل الثنائي أفضل، لأن الرياضيات ضغطت فضاء البحث كله في صيغة مغلقة واحدة.