Let \(a_{i,j}\) be the entry in row \(i\), column \(j\) of an \(80 \times 80\) matrix of positive integers. Starting at the top-left cell and finishing at the bottom-right cell, each move is restricted to one step right or one step down, and the cost of a path is the sum of every visited entry, including the first and last cell.
A brute-force search would have to examine every monotone lattice path from \((0,0)\) to \((79,79)\). There are
$$\binom{158}{79}\approx 2.32\times 10^{46}$$
such paths, so enumeration is hopeless. The key simplification is that any path into a cell \((i,j)\) must arrive either from \((i-1,j)\) or from \((i,j-1)\), which turns the problem into a small dynamic program on the grid itself.
The natural quantity to compute is not the best complete path all at once, but the best partial path ending at each cell. Once those partial optima are known, the answer at the bottom-right corner follows immediately.
Define \(F_{i,j}\) to be the minimum possible path sum from the start \((0,0)\) to the cell \((i,j)\), with both endpoints included in the sum. The final answer is therefore \(F_{79,79}\).
This state is problem-specific and sufficient: if we know the optimal cost to each predecessor of \((i,j)\), then we know everything needed to compute the optimal cost to \((i,j)\) itself.
Along the top row there is no freedom at all: every valid path must keep moving right. Along the left column there is the analogous forced path moving only downward. Therefore the boundary values satisfy
$$F_{0,0}=a_{0,0},\qquad F_{0,j}=F_{0,j-1}+a_{0,j}\quad (j\ge 1),\qquad F_{i,0}=F_{i-1,0}+a_{i,0}\quad (i\ge 1).$$
These formulas are exactly what the implementations use when they initialize the first row and the first column before touching the interior of the matrix.
For any interior cell \((i,j)\) with \(i\ge 1\) and \(j\ge 1\), the last move of a valid path must come from above or from the left. No other predecessor is possible because the path may move only right and down. Hence
$$F_{i,j}=a_{i,j}+\min\!\bigl(F_{i-1,j},F_{i,j-1}\bigr).$$
The proof is the standard optimal-substructure argument. Take an optimal path ending at \((i,j)\). Remove its last cell. What remains must already be an optimal path to whichever predecessor was used; otherwise, replacing that prefix by a cheaper one would produce a cheaper full path, contradicting optimality.
The recurrence depends only on the cell directly above and the cell directly to the left. If we process the grid row by row from top-left to bottom-right, both of those values are already final when \((i,j)\) is updated. Equivalently, the grid with right/down edges is a directed acyclic graph, and row-major order is one valid topological order.
This gives the core invariant behind all three implementations: after a cell has been processed, the stored value at that position is exactly the minimum path sum to that cell. The C++, Python, and Java versions differ only in where they store those values, not in the invariant itself.
The sample matrix used in the problem statement and in the built-in C++ checkpoint is
$$A=\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
After filling the first row and first column, the interior cells are updated by the recurrence. For instance,
$$F_{1,1}=96+\min(804,332)=428,\qquad F_{2,3}=422+\min(1735,1516)=1938.$$
Continuing to the end gives the full dynamic-programming table
$$F=\begin{pmatrix} 131 & 804 & 1038 & 1141 & 1159 \\ 332 & 428 & 770 & 1735 & 1309 \\ 962 & 1231 & 1516 & 1938 & 1420 \\ 1499 & 1930 & 2013 & 2059 & 2376 \\ 2304 & 2662 & 2537 & 2096 & 2427 \end{pmatrix}.$$
So the minimum path sum for the sample is \(2427\). One optimal path is
$$131 \to 201 \to 96 \to 342 \to 746 \to 422 \to 121 \to 37 \to 331,$$
whose total is indeed \(2427\).
The C++, Python, and Java implementations all parse the input as comma-separated rows of integers, then perform exactly the boundary initialization and interior recurrence described above.
Each implementation reads the matrix line by line, splits each line on commas, and converts the resulting tokens to integers. The mathematical object is therefore the same in all three languages: a square grid of weights.
The update order is top-left to bottom-right. The start cell is left unchanged. Then the first row is turned into cumulative sums from left to right, the first column into cumulative sums from top to bottom, and every remaining cell is replaced by its own weight plus the smaller of the already computed top and left totals.
The C++ implementation also includes a small sample verification: before solving the full input, it checks that the sample matrix above produces \(2427\). That checkpoint matches the worked example in the mathematical derivation.
The C++ implementation keeps a separate table of path sums, using a wider integer type for the accumulated totals. The Python and Java implementations instead overwrite the matrix in place, so each entry becomes the minimum path sum to that cell. Both strategies implement the same recurrence and preserve the same invariant; the only difference is whether the original matrix values are kept separately after processing begins.
The running time is \(\Theta(n^2)\) for an \(n \times n\) matrix, because each cell is processed once and each update uses only constant-time arithmetic and one minimum comparison. For the \(80 \times 80\) instance, there are \(6400\) cells and \(6399\) updates after the start cell.
Space depends on the chosen storage strategy. A separate table uses \(\Theta(n^2)\) additional memory, which is what the C++ implementation does. Overwriting the matrix uses \(O(1)\) extra space beyond the input itself, which is what the Python and Java implementations do. A one-row rolling array would reduce the extra space to \(O(n)\) while keeping the same recurrence.
Sei \(a_{i,j}\) der Eintrag in Zeile \(i\), Spalte \(j\) einer \(80 \times 80\)-Matrix positiver Ganzzahlen. Gesucht ist ein Weg von der linken oberen Ecke zur rechten unteren Ecke, bei dem jeder Schritt genau eine Zelle nach rechts oder nach unten geht und die Summe aller besuchten Einträge minimal ist. Sowohl Start- als auch Endzelle zählen zur Summe.
Eine vollständige Suche über alle monotonen Gitterwege wäre aussichtslos. Schon im \(80 \times 80\)-Fall gibt es
$$\binom{158}{79}\approx 2.32\times 10^{46}$$
zulässige Wege. Der entscheidende Punkt ist daher, dass jeder Weg in eine Zelle \((i,j)\) nur von oben oder von links kommen kann. Dadurch wird das Problem zu einer Dynamik direkt auf dem Gitter.
Man berechnet nicht sofort den gesamten optimalen Weg, sondern für jede Zelle die optimale Teilsumme bis zu dieser Zelle. Sobald diese lokalen Optima feststehen, ist die gesuchte Gesamtsumme unten rechts bereits bekannt.
Definiere \(F_{i,j}\) als die minimale Pfadsumme von \((0,0)\) nach \((i,j)\), wobei beide Endpunkte mitgezählt werden. Gesucht ist also schlicht \(F_{79,79}\).
Dieser Zustand ist genau ausreichend: Um \((i,j)\) zu berechnen, braucht man nur die optimalen Werte der möglichen Vorgängerzellen.
In der ersten Zeile kann man sich nur nach rechts bewegen, in der ersten Spalte nur nach unten. Deshalb gelten die Randformeln
$$F_{0,0}=a_{0,0},\qquad F_{0,j}=F_{0,j-1}+a_{0,j}\quad (j\ge 1),\qquad F_{i,0}=F_{i-1,0}+a_{i,0}\quad (i\ge 1).$$
Genau diese erzwungenen Summen werden in den Implementierungen zuerst aufgebaut, bevor die inneren Zellen verarbeitet werden.
Für jede innere Zelle \((i,j)\) mit \(i\ge 1\) und \(j\ge 1\) kann der letzte Schritt eines gültigen Weges nur aus \((i-1,j)\) oder \((i,j-1)\) kommen. Also folgt unmittelbar
$$F_{i,j}=a_{i,j}+\min\!\bigl(F_{i-1,j},F_{i,j-1}\bigr).$$
Der Korrektheitsbeweis ist die übliche Optimalitätsargumentation: Nimmt man von einem optimalen Weg nach \((i,j)\) den letzten Schritt weg, dann muss der verbleibende Präfix bereits optimal zu seinem Endpunkt sein. Wäre er es nicht, könnte man ihn durch einen billigeren Präfix ersetzen und bekäme einen billigeren Gesamtweg.
Die Rekurrenz verwendet nur die obere und die linke Nachbarzelle. Bei einer Verarbeitung von links oben nach rechts unten sind diese beiden Werte bereits endgültig bekannt, wenn \((i,j)\) an der Reihe ist. Man kann das auch als topologische Ordnung eines gerichteten azyklischen Graphen auffassen, dessen Kanten nur nach rechts und nach unten zeigen.
Daraus ergibt sich die Invariante aller drei Implementierungen: Nach der Verarbeitung einer Zelle steht an dieser Position exakt die minimale Pfadsumme bis dorthin. Die Programme unterscheiden sich nur darin, ob diese Werte in einer separaten Tabelle oder direkt in der Matrix gespeichert werden.
Die Beispielmatrix aus der Aufgabenstellung und aus dem eingebauten C++-Checkpoint lautet
$$A=\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
Nach den Randwerten werden die inneren Felder rekursiv gefüllt, etwa
$$F_{1,1}=96+\min(804,332)=428,\qquad F_{2,3}=422+\min(1735,1516)=1938.$$
Am Ende erhält man die Tabelle
$$F=\begin{pmatrix} 131 & 804 & 1038 & 1141 & 1159 \\ 332 & 428 & 770 & 1735 & 1309 \\ 962 & 1231 & 1516 & 1938 & 1420 \\ 1499 & 1930 & 2013 & 2059 & 2376 \\ 2304 & 2662 & 2537 & 2096 & 2427 \end{pmatrix}.$$
Damit ist die minimale Pfadsumme des Beispiels \(2427\). Ein optimaler Weg ist
$$131 \to 201 \to 96 \to 342 \to 746 \to 422 \to 121 \to 37 \to 331,$$
und seine Summe ist tatsächlich \(2427\).
Die C++-, Python- und Java-Implementierungen lesen die Eingabe als kommaseparierte Ganzzahlzeilen ein und führen danach genau die Randinitialisierung und die innere Rekurrenz aus, die oben hergeleitet wurden.
Alle drei Programme zerlegen jede Zeile an den Kommata und wandeln die Teile in ganze Zahlen um. Mathematisch entsteht also in jeder Sprache dasselbe Objekt: ein quadratisches Gitter von Zellgewichten.
Die Verarbeitung läuft von links oben nach rechts unten. Die Startzelle bleibt unverändert. Danach wird die erste Zeile in kumulative Summen von links nach rechts verwandelt, die erste Spalte in kumulative Summen von oben nach unten, und jede innere Zelle erhält ihr eigenes Gewicht plus das Minimum der bereits bekannten Werte von oben und links.
Die C++-Version enthält zusätzlich einen kleinen Beispieltest: Vor der eigentlichen Eingabe wird geprüft, dass die obige 5-mal-5-Matrix den Wert \(2427\) liefert. Dieser Test stimmt genau mit dem durchgerechneten Beispiel überein.
Die C++-Implementierung benutzt eine separate Tabelle für die Pfadsummen und speichert die akkumulierten Werte in einem breiteren Ganzzahltyp. Die Python- und Java-Implementierungen überschreiben dagegen die Matrix direkt, sodass jeder Eintrag nach der Verarbeitung die minimale Pfadsumme bis zu dieser Zelle enthält. Mathematisch ist beides identisch; nur die Speicherorganisation ist verschieden.
Die Laufzeit beträgt \(\Theta(n^2)\) für eine \(n \times n\)-Matrix, weil jede Zelle genau einmal verarbeitet wird und jede Aktualisierung nur konstante Arbeit benötigt. Für \(80 \times 80\) sind das \(6400\) Zellen und nach der Startzelle genau \(6399\) Aktualisierungen.
Der Speicherbedarf hängt von der Darstellung ab. Eine separate Tabelle benötigt \(\Theta(n^2)\) zusätzlichen Speicher, wie in C++. Das Überschreiben der Matrix braucht nur \(O(1)\) Zusatzspeicher über die Eingabe hinaus, wie in Python und Java. Eine Rolling-Array-Variante würde denselben Algorithmus mit \(O(n)\) Zusatzspeicher ausführen.
\(a_{i,j}\), \(80 \times 80\) boyutlu pozitif tam sayı matrisinin \(i\). satır \(j\). sütunundaki değeri olsun. Amaç, sol üst köşeden sağ alt köşeye giderken yalnızca sağa veya aşağı hareket ederek ziyaret edilen bütün hücrelerin toplamını en küçük yapmaktır. Başlangıç ve bitiş hücreleri toplamın içindedir.
Bunu kaba kuvvetle denemek mümkün değildir. \(80 \times 80\) durumunda sağa-aşağı monoton yolların sayısı
$$\binom{158}{79}\approx 2.32\times 10^{46}$$
kadardır. Asıl basitleştirme şudur: \((i,j)\) hücresine gelen her geçerli yol son adımında ya \((i-1,j)\) hücresinden ya da \((i,j-1)\) hücresinden gelmek zorundadır. Böylece problem doğrudan ızgara üzerinde bir dinamik programlama problemine dönüşür.
Tek seferde bütün optimal yolu aramak yerine, her hücreye kadar olan en iyi kısmi toplamı hesaplamak yeterlidir. Sağ alt köşeye gelindiğinde aranan cevap zaten ortaya çıkmış olur.
\(F_{i,j}\), başlangıç \((0,0)\) noktasından \((i,j)\) hücresine kadar olan en küçük yol toplamı olsun. O halde aranan değer doğrudan \(F_{79,79}\)'dur.
Bu durum seçimi tam yeterlidir; çünkü \((i,j)\) için gereken tek bilgi, o hücreye gelebilecek öncüllerin en iyi değerleridir.
İlk satırda yalnızca sağa gidilebilir, ilk sütunda ise yalnızca aşağı inilebilir. Bu yüzden sınır koşulları
$$F_{0,0}=a_{0,0},\qquad F_{0,j}=F_{0,j-1}+a_{0,j}\quad (j\ge 1),\qquad F_{i,0}=F_{i-1,0}+a_{i,0}\quad (i\ge 1)$$
şeklindedir. Uygulamalar da iç hücreleri işlemeye başlamadan önce önce bu zorunlu toplamları kurar.
\(i\ge 1\) ve \(j\ge 1\) için \((i,j)\) hücresine gelen son adım yalnızca üstten veya soldan gelebilir. Başka bir olasılık yoktur. Dolayısıyla
$$F_{i,j}=a_{i,j}+\min\!\bigl(F_{i-1,j},F_{i,j-1}\bigr).$$
Doğruluk gerekçesi optimal alt yapı ilkesidir. \((i,j)\)'de biten optimal bir yol alalım. Son hücreyi çıkarırsak geriye kalan önek, geldiği öncül hücreye kadar zaten optimal olmak zorundadır. Daha ucuz bir önek olsaydı, onunla değiştirerek daha ucuz bir tam yol elde edilirdi.
Bağıntı yalnızca üstteki ve soldaki hücrelere bakar. Hücreler sol üstten sağ alta satır satır işlendiğinde, bu iki değer güncelleme anında zaten kesinleşmiştir. Eşdeğer olarak, yalnızca sağ ve aşağı yönlü kenarlara sahip ızgara yönlü çevrimsiz bir grafiktir ve satır-major sıra geçerli bir topolojik sıradır.
Böylece üç uygulamanın ortak değişmezini elde ederiz: bir hücre işlendiği anda, o konumda saklanan değer o hücreye kadar olan gerçek minimum yol toplamıdır. Diller arasındaki fark yalnızca bu değerin nerede tutulduğudur.
Problem açıklamasındaki ve C++ sürümündeki yerleşik kontrolde kullanılan örnek matris şudur:
$$A=\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
İlk satır ve ilk sütun doldurulduktan sonra iç hücreler bağıntıyla güncellenir. Örneğin
$$F_{1,1}=96+\min(804,332)=428,\qquad F_{2,3}=422+\min(1735,1516)=1938.$$
Sonunda elde edilen DP tablosu
$$F=\begin{pmatrix} 131 & 804 & 1038 & 1141 & 1159 \\ 332 & 428 & 770 & 1735 & 1309 \\ 962 & 1231 & 1516 & 1938 & 1420 \\ 1499 & 1930 & 2013 & 2059 & 2376 \\ 2304 & 2662 & 2537 & 2096 & 2427 \end{pmatrix}.$$
Bu yüzden örnek için minimum yol toplamı \(2427\)'dir. Optimal yollardan biri
$$131 \to 201 \to 96 \to 342 \to 746 \to 422 \to 121 \to 37 \to 331$$
olup toplamı gerçekten \(2427\) eder.
C++, Python ve Java uygulamaları girdiyi virgülle ayrılmış tam sayı satırları olarak okur ve ardından yukarıda türetilen sınır başlangıçlarını ve iç bölge yinelemesini birebir uygular.
Her uygulama satırları tek tek okur, virgüllerden ayırır ve parçaları tam sayıya çevirir. Matematiksel açıdan üçü de aynı nesneyi kurar: hücre ağırlıklarından oluşan kare bir ızgara.
Güncelleme sırası sol üstten sağ alta doğrudur. Başlangıç hücresi olduğu gibi bırakılır. Sonra ilk satır soldan sağa kümülatif toplamlara, ilk sütun yukarıdan aşağı kümülatif toplamlara dönüştürülür ve kalan her hücre kendi ağırlığına, daha önce hesaplanmış üst ve sol toplamların küçüğü eklenerek güncellenir.
C++ uygulaması ayrıca küçük bir örnek doğrulaması içerir: tam veri çözülmeden önce yukarıdaki 5'e 5 matrisin \(2427\) verdiği kontrol edilir. Bu, matematiksel bölümdeki çalışılmış örnekle tam olarak aynıdır.
C++ sürümü yol toplamlarını ayrı bir tabloda tutar ve birikmiş değerler için daha geniş bir tam sayı türü kullanır. Python ve Java sürümleri ise matrisi doğrudan yerinde günceller; böylece her giriş işlendikten sonra o hücreye kadar olan minimum toplamı temsil eder. İki yaklaşımın uyguladığı bağıntı ve koruduğu değişmez aynıdır.
\(n \times n\) bir matris için çalışma süresi \(\Theta(n^2)\)'dir; çünkü her hücre tam bir kez işlenir ve her güncelleme sabit zamanda yapılır. \(80 \times 80\) için \(6400\) hücre vardır ve başlangıç hücresi dışında tam \(6399\) güncelleme yapılır.
Bellek kullanımı depolama biçimine bağlıdır. Ayrı bir tablo \(\Theta(n^2)\) ek alan ister; C++ uygulaması böyledir. Matrisi yerinde güncellemek girişin ötesinde yalnızca \(O(1)\) ek alan gerektirir; Python ve Java uygulamaları böyledir. Tek satırlık kayan dizi sürümü ise aynı bağıntıyla \(O(n)\) ek alan kullanır.
Sea \(a_{i,j}\) la entrada de la fila \(i\) y la columna \(j\) de una matriz \(80 \times 80\) de enteros positivos. Se busca un camino desde la esquina superior izquierda hasta la esquina inferior derecha, moviéndose solo una casilla a la derecha o una casilla hacia abajo en cada paso, de modo que la suma de todas las entradas visitadas sea mínima. La suma incluye tanto la celda inicial como la final.
Un enfoque por fuerza bruta sería inviable. En el caso \(80 \times 80\) existen
$$\binom{158}{79}\approx 2.32\times 10^{46}$$
caminos monótonos posibles. La observación decisiva es que cualquier camino que llegue a la celda \((i,j)\) debe entrar desde \((i-1,j)\) o desde \((i,j-1)\). Eso convierte el problema en una programación dinámica sobre la propia cuadrícula.
No hace falta decidir el camino óptimo completo de una vez. Basta con conocer, para cada celda, la mejor suma posible de un camino parcial que termine allí. Entonces la respuesta aparece en la esquina inferior derecha.
Definimos \(F_{i,j}\) como la suma mínima de un camino desde \((0,0)\) hasta \((i,j)\), contando ambas celdas extremas. Por lo tanto, el valor buscado es \(F_{79,79}\).
Este estado contiene exactamente la información necesaria: para calcular \((i,j)\) solo importa conocer los mejores valores de sus predecesores posibles.
En la primera fila no hay ninguna elección: siempre se avanza hacia la derecha. En la primera columna ocurre lo mismo, pero hacia abajo. Por eso se tiene
$$F_{0,0}=a_{0,0},\qquad F_{0,j}=F_{0,j-1}+a_{0,j}\quad (j\ge 1),\qquad F_{i,0}=F_{i-1,0}+a_{i,0}\quad (i\ge 1).$$
Estas fórmulas de borde son exactamente las que usan las implementaciones antes de procesar el interior de la matriz.
Para una celda interior \((i,j)\) con \(i\ge 1\) y \(j\ge 1\), el último paso de cualquier camino válido solo puede venir desde arriba o desde la izquierda. En consecuencia,
$$F_{i,j}=a_{i,j}+\min\!\bigl(F_{i-1,j},F_{i,j-1}\bigr).$$
La demostración es la subestructura óptima habitual. Si tomamos un camino óptimo que termina en \((i,j)\) y eliminamos su última celda, el prefijo restante ya debe ser óptimo para su predecesor. Si no lo fuera, podríamos sustituirlo por un prefijo más barato y obtener un camino total más barato, lo cual es imposible.
La recurrencia solo depende de la celda superior y de la celda izquierda. Si recorremos la matriz desde la esquina superior izquierda hacia la inferior derecha, esos dos valores ya están fijados cuando actualizamos \((i,j)\). Dicho de otra manera, la cuadrícula con aristas hacia la derecha y hacia abajo forma un grafo acíclico dirigido, y el orden fila por fila es un orden topológico válido.
De ahí sale el invariante común a las tres implementaciones: cuando una celda ha sido procesada, el valor almacenado en esa posición es exactamente la suma mínima de un camino hasta esa celda. Lo único que cambia entre lenguajes es dónde se almacenan esos valores.
La matriz de ejemplo usada en el enunciado y en la comprobación interna de la versión en C++ es
$$A=\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
Después de rellenar la primera fila y la primera columna, las celdas interiores se actualizan con la recurrencia. Por ejemplo,
$$F_{1,1}=96+\min(804,332)=428,\qquad F_{2,3}=422+\min(1735,1516)=1938.$$
Al final se obtiene la tabla dinámica completa
$$F=\begin{pmatrix} 131 & 804 & 1038 & 1141 & 1159 \\ 332 & 428 & 770 & 1735 & 1309 \\ 962 & 1231 & 1516 & 1938 & 1420 \\ 1499 & 1930 & 2013 & 2059 & 2376 \\ 2304 & 2662 & 2537 & 2096 & 2427 \end{pmatrix}.$$
Por tanto, la suma mínima para la muestra es \(2427\). Un camino óptimo es
$$131 \to 201 \to 96 \to 342 \to 746 \to 422 \to 121 \to 37 \to 331,$$
y su suma es precisamente \(2427\).
Las implementaciones en C++, Python y Java leen la entrada como filas de enteros separadas por comas y luego aplican exactamente la inicialización de bordes y la recurrencia interior descritas arriba.
Cada implementación procesa la entrada línea por línea, separa cada fila por comas y convierte los fragmentos en enteros. Matemáticamente, las tres construyen el mismo objeto: una cuadrícula cuadrada de pesos.
El recorrido va de la esquina superior izquierda a la inferior derecha. La celda inicial no cambia. Después, la primera fila se convierte en sumas acumuladas de izquierda a derecha, la primera columna en sumas acumuladas de arriba hacia abajo y cada celda interior se sustituye por su propio peso más el mínimo entre los totales ya calculados arriba y a la izquierda.
La implementación en C++ añade además una verificación pequeña con la muestra: antes de resolver la entrada completa, comprueba que la matriz anterior produce \(2427\). Esa comprobación coincide exactamente con el ejemplo matemático.
La versión en C++ mantiene una tabla separada de sumas mínimas y usa un tipo entero más amplio para los totales acumulados. Las versiones en Python y Java sobrescriben la propia matriz, de modo que cada entrada pasa a representar la suma mínima hasta esa celda. Ambas estrategias implementan la misma recurrencia y preservan el mismo invariante.
El tiempo de ejecución es \(\Theta(n^2)\) para una matriz \(n \times n\), porque cada celda se procesa una vez y cada actualización realiza solo trabajo constante. En la instancia \(80 \times 80\) hay \(6400\) celdas y \(6399\) actualizaciones después de la celda inicial.
La memoria depende de la estrategia elegida. Una tabla separada requiere \(\Theta(n^2)\) memoria adicional, como ocurre en C++. Sobrescribir la matriz usa solo \(O(1)\) espacio extra aparte de la entrada, como hacen Python y Java. Una variante con una sola fila rodante conservaría la misma recurrencia con \(O(n)\) espacio adicional.
设 \(a_{i,j}\) 是一个 \(80 \times 80\) 正整数矩阵中第 \(i\) 行第 \(j\) 列的数。我们从左上角出发，到右下角结束，每一步只能向右或向下移动一格，路径代价定义为路径上所有经过单元格数值之和，起点和终点都计入总和。
如果直接枚举所有合法路径，规模会完全失控。对于 \(80 \times 80\) 的方阵，单调路径的总数是
$$\binom{158}{79}\approx 2.32\times 10^{46}$$
条，显然不可能逐条比较。真正有用的结构是：进入单元格 \((i,j)\) 的最后一步只能来自上方 \((i-1,j)\) 或左方 \((i,j-1)\)。这使得问题可以直接在网格上写成动态规划。
与其一次性寻找完整最优路径，不如先求出“到每个单元格为止的最优部分路径代价”。一旦这些局部最优值全部求出，右下角对应的值就是最终答案。
定义 \(F_{i,j}\) 为从起点 \((0,0)\) 走到单元格 \((i,j)\) 的最小路径和，且起点与终点都包含在求和中。于是题目要求的就是 \(F_{79,79}\)。
这个状态之所以足够，是因为计算 \((i,j)\) 时，只需要知道它可能的前驱单元格的最优值，而不需要保留完整路径本身。
第一行上的路径没有选择，只能一直向右；第一列上的路径同样没有选择，只能一直向下。因此边界满足
$$F_{0,0}=a_{0,0},\qquad F_{0,j}=F_{0,j-1}+a_{0,j}\quad (j\ge 1),\qquad F_{i,0}=F_{i-1,0}+a_{i,0}\quad (i\ge 1).$$
这正是实现中先处理第一行和第一列的原因：这些位置根本不需要做“取最小值”的比较，因为通往它们的合法路径只有一条。
若 \(i\ge 1\) 且 \(j\ge 1\)，那么到达 \((i,j)\) 的最后一步只能来自上方或左方，所以有
$$F_{i,j}=a_{i,j}+\min\!\bigl(F_{i-1,j},F_{i,j-1}\bigr).$$
正确性来自最优子结构。设某条到 \((i,j)\) 的最优路径的最后一步来自某个前驱，那么去掉最后一个单元格后得到的前缀，必然已经是到那个前驱的最优路径；否则可以把它替换成更便宜的前缀，从而得到一条更便宜的完整路径，这与最优性矛盾。
这个递推式只依赖于“上边”和“左边”两个位置。如果按照从左上到右下、逐行逐列的顺序更新，那么计算 \((i,j)\) 时，这两个依赖值都已经是最终正确值。换一个视角看，网格中只允许向右和向下的边，因此它本身就是一个有向无环图，而按行扫描就是一种合法的拓扑序。
由此可以得到三个实现共享的不变式：某个单元格一旦被处理，其当前位置保存的就是到该单元格为止的最小路径和。不同语言实现之间真正不同的，只是这些值保存在独立数组里还是直接写回原矩阵。
题目说明中的样例矩阵，同时也是 C++ 实现内置检查所使用的矩阵，为
$$A=\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
先填完第一行和第一列，再用递推式更新内部单元格。例如
$$F_{1,1}=96+\min(804,332)=428,\qquad F_{2,3}=422+\min(1735,1516)=1938.$$
全部算完后，动态规划表为
$$F=\begin{pmatrix} 131 & 804 & 1038 & 1141 & 1159 \\ 332 & 428 & 770 & 1735 & 1309 \\ 962 & 1231 & 1516 & 1938 & 1420 \\ 1499 & 1930 & 2013 & 2059 & 2376 \\ 2304 & 2662 & 2537 & 2096 & 2427 \end{pmatrix}.$$
因此样例的最小路径和是 \(2427\)。其中一条最优路径对应的数值序列为
$$131 \to 201 \to 96 \to 342 \to 746 \to 422 \to 121 \to 37 \to 331,$$
其总和恰好就是 \(2427\)。
C++、Python 和 Java 三个实现都先把输入按“逗号分隔的整数行”读入，然后严格按照上面推导出的边界初始化和内部递推来更新表格。
三个实现都会逐行读取文本，将每一行按逗号切分，再把切分后的字符串转换为整数。数学上它们建立的是同一个对象：一个带权方格网。
更新顺序都是从左上到右下。起点单元格保持不变。随后第一行被改写成从左到右的前缀和，第一列被改写成从上到下的前缀和，剩余每个单元格则改写为“原权值加上上方与左方最优值中的较小者”。
C++ 实现还额外带有一个小型样例检查：在求解正式输入之前，会先验证上面的 5 乘 5 矩阵确实得到 \(2427\)。这与数学部分的 worked example 完全一致。
C++ 实现使用独立的动态规划表，并用更宽的整数类型保存累积和。Python 与 Java 实现则直接原地覆盖矩阵，使得每个位置在被处理后立即表示“到该单元格的最小路径和”。两种做法遵循同一条递推式，也维护同一个不变式，差别只在存储布局。
对于 \(n \times n\) 矩阵，时间复杂度是 \(\Theta(n^2)\)，因为每个单元格只处理一次，每次更新都只进行常数次运算和一次取最小值比较。对 \(80 \times 80\) 的实例，总共有 \(6400\) 个单元格，除起点外一共进行 \(6399\) 次状态更新。
空间复杂度取决于存储方案。若使用独立表格，则额外空间为 \(\Theta(n^2)\)，这对应 C++ 实现。若直接覆盖输入矩阵，则除了原始矩阵外只需 \(O(1)\) 额外空间，这对应 Python 和 Java 实现。若改用单行滚动数组，同样的递推还可以在 \(O(n)\) 额外空间内完成。
Пусть \(a_{i,j}\) обозначает элемент в строке \(i\) и столбце \(j\) матрицы \(80 \times 80\) из положительных целых чисел. Нужно пройти из верхнего левого угла в нижний правый, двигаясь на каждом шаге только вправо или вниз, и минимизировать сумму всех посещённых значений. В сумму входят и стартовая, и конечная клетки.
Полный перебор всех допустимых путей нереален. Для матрицы \(80 \times 80\) число монотонных путей равно
$$\binom{158}{79}\approx 2.32\times 10^{46}$$
и сравнить их по одному невозможно. Главная структура задачи такова: в клетку \((i,j)\) допустимый путь может прийти только сверху, из \((i-1,j)\), или слева, из \((i,j-1)\). Это и позволяет построить динамику прямо на сетке.
Вместо того чтобы искать весь оптимальный путь сразу, удобнее вычислять оптимальную стоимость частичного пути до каждой клетки. Тогда значение в правом нижнем углу и будет ответом.
Обозначим через \(F_{i,j}\) минимальную сумму пути из \((0,0)\) в \((i,j)\), включая обе крайние клетки. Тогда искомое значение есть \(F_{79,79}\).
Этого состояния достаточно: чтобы вычислить лучшую стоимость для \((i,j)\), нужно знать только лучшие стоимости для его возможных предшественников.
В первой строке можно двигаться только вправо, а в первом столбце только вниз. Поэтому граничные значения задаются формулами
$$F_{0,0}=a_{0,0},\qquad F_{0,j}=F_{0,j-1}+a_{0,j}\quad (j\ge 1),\qquad F_{i,0}=F_{i-1,0}+a_{i,0}\quad (i\ge 1).$$
Именно эти принудительные накопления реализации выполняют вначале, прежде чем переходить к внутренним клеткам.
Если \(i\ge 1\) и \(j\ge 1\), то последний шаг в клетку \((i,j)\) может прийти только сверху или слева. Следовательно,
$$F_{i,j}=a_{i,j}+\min\!\bigl(F_{i-1,j},F_{i,j-1}\bigr).$$
Корректность следует из оптимальной подструктуры. Если взять оптимальный путь до \((i,j)\) и убрать последнюю клетку, то оставшийся префикс уже обязан быть оптимальным путём до соответствующего предшественника. Иначе его можно было бы заменить более дешёвым и получить более дешёвый полный путь, что противоречит оптимальности.
Формула зависит только от верхнего и левого соседа. Если обрабатывать клетки слева направо и сверху вниз, то оба нужных значения уже окончательны в момент обновления \((i,j)\). С точки зрения графов это означает, что сетка с рёбрами только вправо и вниз является ориентированным ациклическим графом, а такой порядок обхода является корректным топологическим порядком.
Отсюда получается общий инвариант всех трёх реализаций: после обработки клетки в ней хранится точная минимальная сумма пути до этой клетки. Разница между языками состоит лишь в том, хранится ли эта информация в отдельной таблице или записывается прямо поверх исходной матрицы.
Примерная матрица из условия, которая также используется во встроенной проверке C++-реализации, такова:
$$A=\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
После заполнения первой строки и первого столбца внутренние клетки вычисляются по рекуррентной формуле. Например,
$$F_{1,1}=96+\min(804,332)=428,\qquad F_{2,3}=422+\min(1735,1516)=1938.$$
В итоге получается полная таблица
$$F=\begin{pmatrix} 131 & 804 & 1038 & 1141 & 1159 \\ 332 & 428 & 770 & 1735 & 1309 \\ 962 & 1231 & 1516 & 1938 & 1420 \\ 1499 & 1930 & 2013 & 2059 & 2376 \\ 2304 & 2662 & 2537 & 2096 & 2427 \end{pmatrix}.$$
Значит, минимальная сумма пути для примера равна \(2427\). Один из оптимальных путей имеет вид
$$131 \to 201 \to 96 \to 342 \to 746 \to 422 \to 121 \to 37 \to 331,$$
и действительно даёт сумму \(2427\).
Реализации на C++, Python и Java читают вход как строки целых чисел, разделённых запятыми, а затем в точности выполняют граничную и внутреннюю динамику, выведенную выше.
Каждая программа разбирает вход построчно, делит строки по запятым и переводит фрагменты в целые числа. С математической точки зрения все три версии создают один и тот же объект: квадратную сетку весов.
Обработка идёт от верхнего левого угла к нижнему правому. Стартовая клетка не меняется. Затем первая строка превращается в накопленные суммы слева направо, первый столбец - в накопленные суммы сверху вниз, а каждая внутренняя клетка заменяется на собственный вес плюс минимум уже найденных сумм сверху и слева.
В C++-реализации есть ещё небольшая контрольная проверка: перед решением основной задачи программа убеждается, что приведённая выше матрица \(5 \times 5\) даёт значение \(2427\). Это полностью совпадает с разобранным примером.
Версия на C++ хранит минимальные суммы в отдельной таблице и использует более широкий целочисленный тип для накопленных значений. Версии на Python и Java переписывают саму матрицу на месте, так что после обработки каждая клетка уже содержит минимальную сумму пути до неё. С точки зрения математики обе стратегии эквивалентны: рекуррентная формула и инвариант остаются одними и теми же.
Время работы равно \(\Theta(n^2)\) для матрицы \(n \times n\), потому что каждая клетка обрабатывается ровно один раз, а каждое обновление занимает константное время. Для случая \(80 \times 80\) это \(6400\) клеток и \(6399\) обновлений после стартовой клетки.
Память зависит от выбранного способа хранения. Отдельная таблица требует \(\Theta(n^2)\) дополнительной памяти, как в C++. Перезапись исходной матрицы использует только \(O(1)\) дополнительной памяти сверх самого входа, как в Python и Java. Вариант с одной скользящей строкой дал бы \(O(n)\) дополнительной памяти при той же самой рекуррентной формуле.
لتكن \(a_{i,j}\) هي قيمة الخلية الموجودة في الصف \(i\) والعمود \(j\) من مصفوفة \(80 \times 80\) من الأعداد الصحيحة الموجبة. المطلوب هو الانتقال من الزاوية العلوية اليسرى إلى الزاوية السفلية اليمنى مع السماح بخطوة واحدة إلى اليمين أو إلى الأسفل فقط في كل مرة، بحيث يكون مجموع القيم على المسار أصغر ما يمكن. وتشمل هذه الكلفة الخليتين الأولى والأخيرة.
الاعتماد على تعداد جميع المسارات غير ممكن عملياً. ففي حالة \(80 \times 80\) يوجد
$$\binom{158}{79}\approx 2.32\times 10^{46}$$
مساراً رتيباً ممكناً. الفكرة الحاسمة هي أن أي مسار يصل إلى الخلية \((i,j)\) لا بد أن تكون خطوته الأخيرة قادمة من الأعلى \((i-1,j)\) أو من اليسار \((i,j-1)\). لهذا السبب يمكن صياغة المسألة كبرمجة ديناميكية مباشرة على الشبكة.
بدلاً من البحث عن المسار الأمثل الكامل دفعة واحدة، نحسب أفضل مجموع جزئي يصل إلى كل خلية. وما إن تُعرف هذه القيم الجزئية المثلى حتى تصبح القيمة في الزاوية السفلية اليمنى هي الجواب المطلوب.
لنعرّف \(F_{i,j}\) بأنه أصغر مجموع مسار من \((0,0)\) إلى \((i,j)\)، مع احتساب الخليتين الطرفيتين في المجموع. إذن الجواب النهائي هو \(F_{79,79}\).
هذا التعريف كافٍ تماماً، لأن حساب أفضل قيمة للخلية \((i,j)\) لا يحتاج إلا إلى أفضل القيم للخلايا التي يمكن الوصول منها إليها مباشرة.
على الصف الأول لا يوجد أي خيار سوى الحركة إلى اليمين، وعلى العمود الأول لا يوجد أي خيار سوى الحركة إلى الأسفل. لذلك نحصل على العلاقات
$$F_{0,0}=a_{0,0},\qquad F_{0,j}=F_{0,j-1}+a_{0,j}\quad (j\ge 1),\qquad F_{i,0}=F_{i-1,0}+a_{i,0}\quad (i\ge 1).$$
ولهذا تبدأ التطبيقات بملء الصف الأول والعمود الأول كمجاميع تراكمية قبل الانتقال إلى الخلايا الداخلية.
إذا كان \(i\ge 1\) و\(j\ge 1\)، فإن الخطوة الأخيرة إلى \((i,j)\) لا يمكن أن تأتي إلا من الأعلى أو من اليسار. ومن ثم
$$F_{i,j}=a_{i,j}+\min\!\bigl(F_{i-1,j},F_{i,j-1}\bigr).$$
وصحة هذه الصيغة تأتي من خاصية البنية المثلى. فإذا أخذنا مساراً أمثل ينتهي عند \((i,j)\) وحذفنا منه الخلية الأخيرة، فإن المقدمة المتبقية يجب أن تكون مساراً أمثل إلى الخليّة السابقة. ولو لم تكن كذلك لاستطعنا استبدالها بمقدمة أرخص والحصول على مسار كامل أرخص، وهذا يناقض الأمثلية.
العلاقة السابقة تعتمد فقط على الجار العلوي والجار الأيسر. وعند معالجة الخلايا من أعلى اليسار إلى أسفل اليمين يكون هذان الجاران قد حُسبا نهائياً قبل الوصول إلى \((i,j)\). ومن منظور الرسوم البيانية، فإن الشبكة التي لا تسمح إلا بالحواف نحو اليمين والأسفل هي رسم بياني موجّه لا دوري، والمرور الصفّي يمثل ترتيباً طوبولوجياً صحيحاً.
ومن هنا نحصل على الثابت المشترك بين التطبيقات الثلاثة: بعد معالجة أي خلية، تصبح القيمة المخزنة في ذلك الموضع مساوية تماماً لأصغر مجموع مسار يصل إليها. الفرق بين اللغات ليس في الرياضيات، بل فقط في مكان تخزين هذه القيم.
المصفوفة التجريبية المستخدمة في نص المسألة، وكذلك في الفحص الداخلي داخل تنفيذ C++، هي
$$A=\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
بعد حساب الصف الأول والعمود الأول، تُملأ الخلايا الداخلية وفق العلاقة السابقة. على سبيل المثال،
$$F_{1,1}=96+\min(804,332)=428,\qquad F_{2,3}=422+\min(1735,1516)=1938.$$
وبعد إكمال الجدول كله نحصل على
$$F=\begin{pmatrix} 131 & 804 & 1038 & 1141 & 1159 \\ 332 & 428 & 770 & 1735 & 1309 \\ 962 & 1231 & 1516 & 1938 & 1420 \\ 1499 & 1930 & 2013 & 2059 & 2376 \\ 2304 & 2662 & 2537 & 2096 & 2427 \end{pmatrix}.$$
إذن أصغر مجموع مسار في المثال هو \(2427\). ومن المسارات المثلى الممكنة
$$131 \to 201 \to 96 \to 342 \to 746 \to 422 \to 121 \to 37 \to 331,$$
ومجموع هذه القيم يساوي فعلاً \(2427\).
تنفيذات C++ وPython وJava كلها تقرأ الإدخال على شكل أسطر من الأعداد الصحيحة المفصولة بفواصل، ثم تطبق بالضبط تهيئة الحدود والعلاقة الداخلية المشتقة أعلاه.
كل تنفيذ يقرأ الأسطر واحداً واحداً، ثم يقسم كل سطر عند الفواصل، ثم يحول المقاطع إلى أعداد صحيحة. ومن الناحية الرياضية فإن اللغات الثلاث تبني الكائن نفسه: شبكة مربعة من الأوزان.
يتم التحديث من الزاوية العلوية اليسرى إلى الزاوية السفلية اليمنى. خلية البداية تبقى كما هي. بعد ذلك يتحول الصف الأول إلى مجاميع تراكمية من اليسار إلى اليمين، ويتحول العمود الأول إلى مجاميع تراكمية من الأعلى إلى الأسفل، ثم تُستبدل كل خلية داخلية بوزنها الأصلي مضافاً إليه الأصغر بين المجموعين المحسوبين سابقاً من الأعلى ومن اليسار.
ويحتوي تنفيذ C++ أيضاً على تحقق صغير باستخدام المثال: قبل حل الإدخال الكامل يتأكد من أن المصفوفة \(5\times 5\) السابقة تعطي \(2427\). وهذا يطابق تماماً المثال الرياضي المفصل.
تنفيذ C++ يحتفظ بجدول منفصل لمجاميع المسارات ويستخدم نوعاً عددياً أوسع للقيم التراكمية. أما تنفيذَا Python وJava فيكتبان النتائج فوق المصفوفة نفسها، بحيث تصبح كل خلية بعد معالجتها مساوية لأصغر مجموع يصل إليها. الطريقتان تنفذان العلاقة نفسها وتحافظان على الثابت نفسه؛ الاختلاف الوحيد هو تنظيم الذاكرة.
زمن التنفيذ هو \(\Theta(n^2)\) لمصفوفة \(n \times n\)، لأن كل خلية تُعالج مرة واحدة فقط، وكل تحديث يحتاج إلى عمل ثابت وزمن ثابت. في حالة \(80 \times 80\) لدينا \(6400\) خلية و\(6399\) تحديثاً بعد خلية البداية.
أما الذاكرة فتعتمد على طريقة التخزين. استخدام جدول منفصل يحتاج إلى \(\Theta(n^2)\) من الذاكرة الإضافية، وهذا ما تفعله نسخة C++. والكتابة في مكانها داخل المصفوفة تحتاج إلى \(O(1)\) ذاكرة إضافية فوق الإدخال نفسه، وهذا ما تفعله نسختا Python وJava. ويمكن أيضاً استعمال صف متدحرج واحد للوصول إلى \(O(n)\) ذاكرة إضافية مع الحفاظ على العلاقة نفسها.