We are given a square matrix of positive integers. A valid path may start in any row of the first column and end in any row of the last column. The allowed moves are right, up, and down, but never left. The objective is to minimize the sum of all entries visited by the path.
The extra difficulty, compared with a purely right-and-down problem, is that vertical motion is allowed inside a column. That means the best value for one cell in a column depends on other cells in the same column, so the natural state is not a single cell but the whole frontier formed by one processed column.
Let \(M_{r,c}\) denote the matrix entry in row \(r\), column \(c\), with \(0 \le r,c < n\). After processing column \(c\), define \(D^{(c)}_r\) to be the minimum path sum among all valid paths that end at cell \((r,c)\). The final answer is therefore
$$\min_{0 \le r < n} D^{(n-1)}_r.$$
In the first column nothing has happened yet: every row is an admissible starting point. Hence the initial state is simply
$$D^{(0)}_r = M_{r,0} \qquad (0 \le r < n).$$
This is the invariant the implementations maintain: once column \(c\) has been finished, the vector \(D^{(c)}\) contains the exact optimal costs for reaching every row of that column.
Fix a column \(c \ge 1\) and assume the previous vector \(D^{(c-1)}\) is already known. Any path that ends at row \(r\) of the new column must enter column \(c\) from the left at some row \(k\), paying \(D^{(c-1)}_k + M_{k,c}\), and then move vertically inside column \(c\) until it reaches row \(r\).
Because all matrix entries are positive and left moves are forbidden, an optimal path never changes vertical direction inside a single column. If it moved up and later down again, or down and later up again, then some row in that column would be visited twice, producing a positive detour that can be removed. So the vertical segment inside one column is always monotone.
That observation gives the exact one-column formula:
$$D^{(c)}_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right).$$
For each possible entry row \(k\), we pay the best cost to reach the previous column at row \(k\), then we add precisely the cells traversed in column \(c\) from row \(k\) to row \(r\).
The formula naturally splits into two families of candidates. If \(k \le r\), the path enters at row \(k\) and moves only downward inside the new column, contributing
$$D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}.$$
If \(k \ge r\), the path enters at row \(k\) and moves only upward, contributing
$$D^{(c-1)}_k + \sum_{t=r}^{k} M_{t,c}.$$
The implementations begin with the direct-right candidate
$$T_r = D^{(c-1)}_r + M_{r,c}.$$
Then they sweep from top to bottom:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r-1} + M_{r,c}\bigr)\qquad (r=1,2,\dots,n-1).$$
After this pass, every downward-only possibility has been absorbed, so
$$T_r = \min_{0 \le k \le r}\left(D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}\right).$$
A second sweep from bottom to top handles the upward-only possibilities:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r+1} + M_{r,c}\bigr)\qquad (r=n-2,n-3,\dots,0).$$
When that pass ends, we have exactly
$$T_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right)=D^{(c)}_r.$$
So the two sweeps are not a heuristic shortcut; they are a compact way to evaluate the full minimum over all possible entry rows.
For the sample matrix
$$\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}$$
the first column gives
$$D^{(0)} = (131, 201, 630, 537, 805).$$
In column 1, the direct-right candidates are
$$T = (804, 297, 1433, 1236, 1537).$$
The downward sweep improves row 2, producing
$$T = (804, 297, 1100, 1236, 1537),$$
and the upward sweep changes nothing further, so
$$D^{(1)} = (804, 297, 1100, 1236, 1537).$$
Column 2 is a good illustration of why both directions matter. The direct-right vector is
$$T = (1038, 639, 1846, 1733, 2061).$$
After the downward sweep it becomes
$$T = (1038, 639, 1385, 1733, 2061),$$
and the upward sweep then improves the first row to
$$D^{(2)} = (873, 639, 1385, 1733, 2061).$$
That improvement comes from entering column 2 at row 1 with cost \(639\) and then moving upward through the value \(234\).
Continuing this process to the last column gives
$$D^{(4)} = (994, 1144, 1255, 2211, 2222).$$
Hence the sample minimum is
$$\min_r D^{(4)}_r = 994,$$
realized by the path \(201 \to 96 \to 342 \to 234 \to 103 \to 18\).
The C++, Python, and Java implementations all read the CSV matrix into a two-dimensional array and keep a one-dimensional dynamic-programming vector for the current column. That vector starts as the first column itself, because any row there can be chosen as the starting position.
For each later column, the implementation first forms the direct-right candidates by adding the new column entry to every row. It then performs one top-to-bottom relaxation and one bottom-to-top relaxation, which exactly match the two monotone cases in the derivation above. After the final column has been processed, the minimum value in the vector is the minimum path sum from the left edge to the right edge.
Each new column is handled by three linear passes over the rows: one initialization pass, one downward sweep, and one upward sweep. For an \(n \times n\) matrix, that is \(O(n)\) work per column and \(O(n^2)\) time overall.
The extra working memory is \(O(n)\), because the algorithm only needs the current column-cost vector in addition to the input matrix. For the \(80 \times 80\) instance in the problem, this is comfortably fast and avoids the extra overhead of running a fully general shortest-path routine on the whole grid graph.
Gegeben ist eine quadratische Matrix positiver ganzer Zahlen. Ein zulässiger Pfad darf in einer beliebigen Zeile der ersten Spalte beginnen und in einer beliebigen Zeile der letzten Spalte enden. Erlaubt sind die Bewegungen nach rechts, nach oben und nach unten, aber niemals nach links. Gesucht ist die minimale Summe aller besuchten Matrixeinträge.
Die eigentliche Schwierigkeit besteht darin, dass innerhalb einer Spalte vertikale Bewegungen erlaubt sind. Deshalb hängt der beste Wert für eine Zelle nicht nur von der linken Nachbarzelle ab, sondern von mehreren möglichen Eintrittszeilen derselben Spalte. Die natürliche dynamische Zustandsgröße ist also eine ganze Spalte und nicht nur eine einzelne Zelle.
Sei \(M_{r,c}\) der Matrixeintrag in Zeile \(r\) und Spalte \(c\), mit \(0 \le r,c < n\). Nach der Verarbeitung der Spalte \(c\) bezeichne \(D^{(c)}_r\) die minimale Pfadsumme unter allen zulässigen Pfaden, die in der Zelle \((r,c)\) enden. Die gesuchte Antwort ist damit
$$\min_{0 \le r < n} D^{(n-1)}_r.$$
In der ersten Spalte wurde noch keine Bewegung ausgeführt; jede Zeile kann direkt als Startzeile gewählt werden. Daher gilt zunächst
$$D^{(0)}_r = M_{r,0} \qquad (0 \le r < n).$$
Genau diese Invariante halten die Implementierungen fest: Sobald Spalte \(c\) abgeschlossen ist, enthält der Vektor \(D^{(c)}\) die exakten optimalen Kosten, um jede Zeile dieser Spalte zu erreichen.
Fixiere eine Spalte \(c \ge 1\) und nehme an, dass der vorherige Vektor \(D^{(c-1)}\) schon bekannt ist. Jeder Pfad, der in Zeile \(r\) der neuen Spalte endet, muss Spalte \(c\) von links in irgendeiner Zeile \(k\) betreten. Dafür zahlt er zunächst \(D^{(c-1)}_k + M_{k,c}\) und bewegt sich dann innerhalb der Spalte \(c\) vertikal bis zur Zeile \(r\).
Weil alle Matrixeinträge positiv sind und Linksbewegungen verboten sind, ändert ein optimaler Pfad innerhalb einer einzelnen Spalte niemals die vertikale Richtung. Würde er erst nach oben und später wieder nach unten gehen oder umgekehrt, dann würde er eine Zeile derselben Spalte doppelt besuchen. Dieser Umweg hätte positive Kosten und könnte gestrichen werden.
Damit ist der vertikale Teil in einer Spalte immer monoton, und man erhält die exakte Formel
$$D^{(c)}_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right).$$
Für jede mögliche Eintrittszeile \(k\) nimmt man also die besten Kosten bis zur vorherigen Spalte und addiert genau die Einträge der neuen Spalte, die auf dem vertikalen Weg von \(k\) nach \(r\) liegen.
Die Formel zerfällt in zwei natürliche Fälle. Für \(k \le r\) betritt der Pfad die neue Spalte in Zeile \(k\) und bewegt sich nur nach unten. Sein Beitrag ist
$$D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}.$$
Für \(k \ge r\) betritt der Pfad die Spalte in Zeile \(k\) und bewegt sich nur nach oben. Dann erhält man
$$D^{(c-1)}_k + \sum_{t=r}^{k} M_{t,c}.$$
Die Implementierungen beginnen mit dem direkten Rechts-Schritt
$$T_r = D^{(c-1)}_r + M_{r,c}.$$
Anschließend folgt ein Sweep von oben nach unten:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r-1} + M_{r,c}\bigr)\qquad (r=1,2,\dots,n-1).$$
Nach diesem Durchlauf sind alle rein abwärts gerichteten Möglichkeiten erfasst, also
$$T_r = \min_{0 \le k \le r}\left(D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}\right).$$
Ein zweiter Sweep von unten nach oben fügt die rein aufwärts gerichteten Möglichkeiten hinzu:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r+1} + M_{r,c}\bigr)\qquad (r=n-2,n-3,\dots,0).$$
Danach gilt exakt
$$T_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right)=D^{(c)}_r.$$
Die beiden Sweeps sind also keine Näherung, sondern eine kompakte Auswertung des vollständigen Minimums über alle Eintrittszeilen.
Für die Beispielmatrix
$$\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}$$
liefert die erste Spalte
$$D^{(0)} = (131, 201, 630, 537, 805).$$
In Spalte 1 ergeben direkte Rechts-Schritte zunächst
$$T = (804, 297, 1433, 1236, 1537).$$
Der Abwärts-Sweep verbessert Zeile 2 zu
$$T = (804, 297, 1100, 1236, 1537),$$
während der Aufwärts-Sweep nichts weiter ändert. Also ist
$$D^{(1)} = (804, 297, 1100, 1236, 1537).$$
Spalte 2 zeigt besonders deutlich, warum beide Richtungen notwendig sind. Der direkte Vektor ist
$$T = (1038, 639, 1846, 1733, 2061).$$
Nach dem Abwärts-Sweep erhält man
$$T = (1038, 639, 1385, 1733, 2061),$$
und erst der Aufwärts-Sweep verbessert dann die erste Zeile auf
$$D^{(2)} = (873, 639, 1385, 1733, 2061).$$
Diese Verbesserung entsteht dadurch, dass man Spalte 2 in Zeile 1 mit Kosten \(639\) betritt und dann nach oben durch den Eintrag \(234\) geht.
Führt man das Verfahren bis zur letzten Spalte fort, so erhält man
$$D^{(4)} = (994, 1144, 1255, 2211, 2222).$$
Damit ist das Beispielminimum
$$\min_r D^{(4)}_r = 994,$$
realisiert durch den Pfad \(201 \to 96 \to 342 \to 234 \to 103 \to 18\).
Die C++-, Python- und Java-Implementierungen lesen die CSV-Matrix in ein zweidimensionales Array ein und halten einen eindimensionalen DP-Vektor für die aktuell verarbeitete Spalte. Dieser Vektor beginnt mit den Werten der ersten Spalte selbst, weil dort jede Zeile als Startpunkt zulässig ist.
Für jede weitere Spalte werden zunächst die direkten Rechts-Kandidaten gebildet, indem der neue Spalteneintrag zu jeder Zeile addiert wird. Danach folgen genau zwei Relaxationsdurchläufe: einmal von oben nach unten und einmal von unten nach oben. Diese beiden Durchläufe entsprechen exakt den beiden monotonen Fällen der Herleitung. Nach der letzten Spalte ist das Minimum im Vektor die gesuchte minimale Pfadsumme vom linken zum rechten Rand.
Jede neue Spalte wird mit drei linearen Durchläufen über die Zeilen verarbeitet: Initialisierung, Abwärts-Sweep und Aufwärts-Sweep. Für eine \(n \times n\)-Matrix ergibt das \(O(n)\) Arbeit pro Spalte und insgesamt \(O(n^2)\) Zeit.
Der zusätzliche Arbeitspeicher beträgt \(O(n)\), weil außer der Eingabematrix nur der aktuelle Kostenvektor gehalten werden muss. Für die \(80 \times 80\)-Instanz der Aufgabe ist dieses Verfahren problemlos schnell und vermeidet den zusätzlichen Aufwand eines vollständig allgemeinen Kürzeste-Wege-Algorithmus auf dem gesamten Gittergraphen.
Elimizde pozitif tamsayılardan oluşan kare bir matris vardır. Geçerli bir yol, ilk sütundaki herhangi bir satırdan başlayıp son sütundaki herhangi bir satırda bitebilir. İzin verilen hareketler sağa, yukarı ve aşağıdır; sola gitmek yasaktır. Amaç, yol boyunca ziyaret edilen tüm hücrelerin toplamını en küçük yapmaktır.
Saf sağ ve aşağı hareketli problemlere göre asıl fark şudur: bir sütunun içinde dikey hareket serbesttir. Bu yüzden bir hücrenin en iyi değeri yalnızca sol komşusuna bağlı değildir; aynı sütuna hangi satırdan girildiği de önemlidir. Doğal dinamik programlama durumu tek bir hücre değil, işlenmiş bir sütunun tamamıdır.
\(M_{r,c}\), \(r\). satır ve \(c\). sütundaki değer olsun; burada \(0 \le r,c < n\). Sütun \(c\) işlendiğinde, \(D^{(c)}_r\) değerini \((r,c)\) hücresinde biten tüm geçerli yollar arasındaki en küçük yol toplamı olarak tanımlayalım. O halde aranan cevap
$$\min_{0 \le r < n} D^{(n-1)}_r$$
olur.
İlk sütunda henüz hiçbir hareket yapılmamıştır; her satır doğrudan başlangıç satırı olabilir. Bu nedenle başlangıç durumu
$$D^{(0)}_r = M_{r,0} \qquad (0 \le r < n)$$
şeklindedir. Uygulamaların koruduğu değişmez de budur: sütun \(c\) tamamlandığında \(D^{(c)}\) vektörü, o sütundaki her satıra ulaşmanın tam en iyi maliyetini içerir.
\(c \ge 1\) olan sabit bir sütun düşünelim ve önceki vektör \(D^{(c-1)}\) değerlerinin bilindiğini varsayalım. Yeni sütunun \(r\). satırında biten her yol, sütun \(c\)'ye soldan bir \(k\) satırından girmek zorundadır. Bunun maliyeti önce \(D^{(c-1)}_k + M_{k,c}\) olur, sonra yol sütun \(c\) içinde dikey olarak \(r\). satıra kadar ilerler.
Tüm matris girişleri pozitif ve sola gitmek yasak olduğu için, tek bir sütun içindeki optimal yol dikey yönünü asla değiştirmez. Eğer önce yukarı sonra aşağı, ya da önce aşağı sonra yukarı gitseydi, aynı sütundaki bir satır iki kez ziyaret edilmiş olurdu. Bu da pozitif maliyetli gereksiz bir dolambaç yaratır ve çıkarılabilir.
Dolayısıyla bir sütun içindeki dikey bölüm daima monotondur ve tam geçiş formülü
$$D^{(c)}_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right)$$
olur. Yani her olası giriş satırı \(k\) için, önce önceki sütuna kadar olan en iyi maliyeti alırız; sonra da yeni sütunda \(k\) ile \(r\) arasındaki tam dikey parçayı ekleriz.
Bu formül doğal olarak iki aday ailesine ayrılır. \(k \le r\) ise yol yeni sütuna \(k\) satırından girer ve sadece aşağı iner. Katkısı
$$D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}$$
olur. \(k \ge r\) ise yol \(k\) satırından girer ve sadece yukarı çıkar. Bu durumda katkı
$$D^{(c-1)}_k + \sum_{t=r}^{k} M_{t,c}$$
şeklindedir.
Uygulamalar önce doğrudan sağa geçiş adayını kurar:
$$T_r = D^{(c-1)}_r + M_{r,c}.$$
Daha sonra yukarıdan aşağıya bir tarama yapılır:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r-1} + M_{r,c}\bigr)\qquad (r=1,2,\dots,n-1).$$
Bu geçişten sonra yalnızca aşağı yönlü tüm olasılıklar hesaba katılmış olur ve
$$T_r = \min_{0 \le k \le r}\left(D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}\right)$$
eşitliği elde edilir. Ardından aşağıdan yukarıya ikinci tarama gelir:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r+1} + M_{r,c}\bigr)\qquad (r=n-2,n-3,\dots,0).$$
Bu ikinci geçiş bittiğinde tam olarak
$$T_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right)=D^{(c)}_r$$
elde edilir. Yani iki tarama sezgisel bir kestirme değil, bütün giriş satırları üzerindeki gerçek minimumun sıkıştırılmış hesabıdır.
Örnek matris için
$$\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}$$
ilk sütun
$$D^{(0)} = (131, 201, 630, 537, 805)$$
vektörünü verir. Sütun 1 için doğrudan sağa geçiş adayları
$$T = (804, 297, 1433, 1236, 1537)$$
olur. Aşağı tarama 2. satırı iyileştirerek
$$T = (804, 297, 1100, 1236, 1537)$$
vektörünü üretir; yukarı tarama ise başka değişiklik yapmaz. Dolayısıyla
$$D^{(1)} = (804, 297, 1100, 1236, 1537)$$
elde edilir.
Sütun 2, iki yönün de neden gerekli olduğunu iyi gösterir. Doğrudan vektör
$$T = (1038, 639, 1846, 1733, 2061)$$
iken, aşağı taramadan sonra
$$T = (1038, 639, 1385, 1733, 2061)$$
olur; ardından yukarı tarama ilk satırı iyileştirerek
$$D^{(2)} = (873, 639, 1385, 1733, 2061)$$
sonucunu verir. Bu iyileşme, sütun 2'ye 1. satırdan \(639\) maliyetle girip sonra \(234\) değerinden yukarı geçmekten gelir.
İşleme son sütuna kadar devam edildiğinde
$$D^{(4)} = (994, 1144, 1255, 2211, 2222)$$
elde edilir. Böylece örnek minimum
$$\min_r D^{(4)}_r = 994$$
olur ve bunu veren yol \(201 \to 96 \to 342 \to 234 \to 103 \to 18\) yoludur.
C++, Python ve Java uygulamaları CSV matrisini iki boyutlu bir diziye okur ve o anda işlenen sütun için tek boyutlu bir DP vektörü tutar. Bu vektör ilk sütunun kendisiyle başlar; çünkü ilk sütundaki her satır geçerli bir başlangıç noktasıdır.
Her yeni sütunda uygulama önce doğrudan sağa geçiş adaylarını kurmak için yeni sütun değerini bütün satırlara ekler. Sonra yukarıdan aşağıya ve aşağıdan yukarıya birer gevşetme geçişi yapar. Bu iki geçiş, yukarıdaki türetimdeki iki monoton durumun tam karşılığıdır. Son sütun bittiğinde, vektördeki en küçük değer soldan sağ kenara olan minimum yol toplamıdır.
Her yeni sütun, satırlar üzerinde üç doğrusal geçişle işlenir: başlangıç geçişi, aşağı tarama ve yukarı tarama. \(n \times n\) boyutlu bir matris için bu, sütun başına \(O(n)\) ve toplamda \(O(n^2)\) zaman demektir.
Ek çalışma belleği \(O(n)\) düzeyindedir; çünkü giriş matrisine ek olarak yalnızca güncel sütun maliyet vektörü gerekir. Sorudaki \(80 \times 80\) örnek için bu yöntem oldukça hızlıdır ve tüm ızgara üzerinde genel amaçlı bir en kısa yol algoritması çalıştırmanın ek yükünü taşımaz.
Se da una matriz cuadrada de enteros positivos. Un camino válido puede comenzar en cualquier fila de la primera columna y terminar en cualquier fila de la última columna. Los movimientos permitidos son a la derecha, hacia arriba y hacia abajo, pero nunca hacia la izquierda. El objetivo es minimizar la suma de todas las entradas visitadas.
La dificultad adicional, frente a un problema donde solo se puede ir a la derecha y hacia abajo, es que dentro de una misma columna sí se permite movimiento vertical. Por eso, el mejor valor para una celda no depende solo de su vecino izquierdo, sino también de varias filas posibles de entrada en esa columna. El estado natural del método es toda una columna ya procesada.
Sea \(M_{r,c}\) la entrada de la matriz en la fila \(r\) y la columna \(c\), con \(0 \le r,c < n\). Después de procesar la columna \(c\), definimos \(D^{(c)}_r\) como la mínima suma de camino entre todos los caminos válidos que terminan en la celda \((r,c)\). La respuesta final es entonces
$$\min_{0 \le r < n} D^{(n-1)}_r.$$
En la primera columna todavía no ha ocurrido ningún movimiento: cualquier fila puede elegirse como punto de partida. Por tanto, el estado inicial es
$$D^{(0)}_r = M_{r,0} \qquad (0 \le r < n).$$
Esa es exactamente la invariante que mantienen las implementaciones: una vez terminada la columna \(c\), el vector \(D^{(c)}\) contiene los costos óptimos exactos para llegar a cada fila de esa columna.
Fijemos una columna \(c \ge 1\) y supongamos conocido el vector anterior \(D^{(c-1)}\). Todo camino que termina en la fila \(r\) de la nueva columna debe entrar en la columna \(c\) desde la izquierda por alguna fila \(k\). Para ello paga primero \(D^{(c-1)}_k + M_{k,c}\) y luego se mueve verticalmente dentro de la columna \(c\) hasta alcanzar la fila \(r\).
Como todas las entradas de la matriz son positivas y está prohibido ir a la izquierda, un camino óptimo nunca cambia de dirección vertical dentro de una sola columna. Si subiera y después bajara, o bajara y después subiera, visitaría dos veces alguna fila de esa columna. Ese rodeo tiene costo positivo y puede eliminarse.
Por tanto, el tramo vertical dentro de una columna siempre es monótono, y obtenemos la fórmula exacta
$$D^{(c)}_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right).$$
Para cada posible fila de entrada \(k\), tomamos el mejor costo hasta la columna anterior y añadimos exactamente las celdas atravesadas en la columna \(c\) al movernos desde \(k\) hasta \(r\).
La fórmula se divide de forma natural en dos familias de candidatos. Si \(k \le r\), el camino entra en la nueva columna por la fila \(k\) y luego solo baja. Su contribución es
$$D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}.$$
Si \(k \ge r\), el camino entra por la fila \(k\) y luego solo sube. En ese caso la contribución es
$$D^{(c-1)}_k + \sum_{t=r}^{k} M_{t,c}.$$
Las implementaciones comienzan con el candidato de ir directamente a la derecha:
$$T_r = D^{(c-1)}_r + M_{r,c}.$$
Después hacen un barrido de arriba hacia abajo:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r-1} + M_{r,c}\bigr)\qquad (r=1,2,\dots,n-1).$$
Al terminar esa pasada, ya se han incorporado todas las posibilidades puramente descendentes, de modo que
$$T_r = \min_{0 \le k \le r}\left(D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}\right).$$
Un segundo barrido de abajo hacia arriba añade las posibilidades puramente ascendentes:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r+1} + M_{r,c}\bigr)\qquad (r=n-2,n-3,\dots,0).$$
Al final de esa segunda pasada se obtiene exactamente
$$T_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right)=D^{(c)}_r.$$
Así que los dos barridos no son una aproximación: son una manera compacta de evaluar el mínimo completo sobre todas las filas posibles de entrada.
Para la matriz de ejemplo
$$\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}$$
la primera columna produce
$$D^{(0)} = (131, 201, 630, 537, 805).$$
En la columna 1, los candidatos de ir directamente a la derecha son
$$T = (804, 297, 1433, 1236, 1537).$$
El barrido descendente mejora la fila 2 y deja
$$T = (804, 297, 1100, 1236, 1537),$$
mientras que el barrido ascendente ya no cambia nada. Por tanto,
$$D^{(1)} = (804, 297, 1100, 1236, 1537).$$
La columna 2 muestra bien por qué hacen falta ambas direcciones. El vector directo es
$$T = (1038, 639, 1846, 1733, 2061).$$
Tras el barrido de arriba hacia abajo pasa a
$$T = (1038, 639, 1385, 1733, 2061),$$
y luego el barrido de abajo hacia arriba mejora la primera fila hasta
$$D^{(2)} = (873, 639, 1385, 1733, 2061).$$
Esa mejora aparece porque conviene entrar en la columna 2 por la fila 1 con costo \(639\) y luego subir atravesando el valor \(234\).
Si continuamos hasta la última columna obtenemos
$$D^{(4)} = (994, 1144, 1255, 2211, 2222).$$
En consecuencia, el mínimo del ejemplo es
$$\min_r D^{(4)}_r = 994,$$
realizado por el camino \(201 \to 96 \to 342 \to 234 \to 103 \to 18\).
Las implementaciones en C++, Python y Java leen la matriz CSV en un arreglo bidimensional y mantienen un vector unidimensional de programación dinámica para la columna actual. Ese vector empieza siendo la propia primera columna, porque cualquier fila de esa columna puede elegirse como inicio.
Para cada columna posterior, la implementación forma primero los candidatos de movimiento directo a la derecha sumando la nueva entrada de columna en cada fila. Después ejecuta una relajación de arriba hacia abajo y otra de abajo hacia arriba. Esas dos pasadas coinciden exactamente con los dos casos monótonos de la derivación matemática. Una vez procesada la última columna, el valor mínimo del vector es la mínima suma de camino desde el borde izquierdo hasta el borde derecho.
Cada columna nueva se procesa con tres pasadas lineales sobre las filas: una pasada de inicialización, un barrido descendente y un barrido ascendente. Para una matriz \(n \times n\), eso implica \(O(n)\) trabajo por columna y \(O(n^2)\) tiempo total.
La memoria de trabajo adicional es \(O(n)\), porque además de la matriz de entrada solo se necesita el vector de costos de la columna actual. Para la instancia \(80 \times 80\) del problema, este método es holgadamente suficiente y evita el sobrecoste de aplicar un algoritmo de caminos mínimos completamente general sobre todo el grafo de la cuadrícula.
题目给出一个由正整数组成的方阵。合法路径可以从最左列的任意一行出发，在最右列的任意一行结束。允许的移动只有向右、向上和向下，不能向左。目标是让路径经过的所有数字之和尽可能小。
与只能向右和向下的情形相比，这一题真正麻烦的地方在于：在同一列内部允许上下移动。于是，一格的最优值不再只取决于它左边那一格，而是取决于“这一列从哪一行进入”。因此最自然的动态规划状态不是单个格子，而是“某一整列处理完成后的整条边界”。
记 \(M_{r,c}\) 为第 \(r\) 行、第 \(c\) 列的矩阵元素，其中 \(0 \le r,c < n\)。当第 \(c\) 列处理完成后，定义 \(D^{(c)}_r\) 为所有合法路径中终点落在单元格 \((r,c)\) 时的最小路径和。于是最后的答案就是
$$\min_{0 \le r < n} D^{(n-1)}_r.$$
在第一列中，路径还没有发生任何移动；每一行都可以直接作为起点。因此初始状态非常简单：
$$D^{(0)}_r = M_{r,0} \qquad (0 \le r < n).$$
这正是实现中维护的不变量：一旦第 \(c\) 列处理结束，向量 \(D^{(c)}\) 就精确记录了到达该列每一行的最优代价。
固定某一列 \(c \ge 1\)，并假设前一列的向量 \(D^{(c-1)}\) 已经知道。任何一个最终停在新列第 \(r\) 行的路径，都必须先从左边进入第 \(c\) 列的某个第 \(k\) 行，先付出 \(D^{(c-1)}_k + M_{k,c}\)，然后再在第 \(c\) 列内部沿着竖直方向走到第 \(r\) 行。
由于矩阵中的数全是正数，而且禁止向左，所以在同一列内部的最优路径绝不会先向上再向下，或先向下再向上。只要竖直方向发生了反转，就意味着该列中的某一行被重复经过，从而形成一个正代价的绕路；删掉这段绕路后，路径只会更短。
因此，在单列内部的竖直部分一定是单调的，进而得到精确公式
$$D^{(c)}_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right).$$
这意味着：对于每个可能的入列行 \(k\)，我们取到达前一列该行的最优代价，再加上在新列中从 \(k\) 走到 \(r\) 必须经过的那一整段数字。
上面的最小值天然分成两类候选。若 \(k \le r\)，则路径从第 \(k\) 行进入新列后只会向下移动，贡献为
$$D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}.$$
若 \(k \ge r\)，则路径从第 \(k\) 行进入后只会向上移动，贡献为
$$D^{(c-1)}_k + \sum_{t=r}^{k} M_{t,c}.$$
实现首先建立“直接向右”的候选值：
$$T_r = D^{(c-1)}_r + M_{r,c}.$$
随后做一次从上到下的扫描：
$$T_r \leftarrow \min\bigl(T_r,\; T_{r-1} + M_{r,c}\bigr)\qquad (r=1,2,\dots,n-1).$$
这一步结束后，所有“从上方某行进入并一路向下”的情况都已经吸收进来了，因此
$$T_r = \min_{0 \le k \le r}\left(D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}\right).$$
再做一次从下到上的扫描：
$$T_r \leftarrow \min\bigl(T_r,\; T_{r+1} + M_{r,c}\bigr)\qquad (r=n-2,n-3,\dots,0).$$
当第二次扫描结束时，就得到严格的等式
$$T_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right)=D^{(c)}_r.$$
所以两次扫描并不是经验技巧，而是对“所有可能入列行的完整最小值”所做的一种紧凑计算。
对示例矩阵
$$\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}$$
第一列直接给出
$$D^{(0)} = (131, 201, 630, 537, 805).$$
处理第 1 列时，直接向右得到的候选是
$$T = (804, 297, 1433, 1236, 1537).$$
自上而下扫描会把第 2 行改进为
$$T = (804, 297, 1100, 1236, 1537),$$
而自下而上扫描不再产生新的改进，因此
$$D^{(1)} = (804, 297, 1100, 1236, 1537).$$
第 2 列更能说明为什么两个方向都不可少。直接向右的向量是
$$T = (1038, 639, 1846, 1733, 2061).$$
向下扫描之后变成
$$T = (1038, 639, 1385, 1733, 2061),$$
接着向上扫描又把第一行改进成
$$D^{(2)} = (873, 639, 1385, 1733, 2061).$$
这一改进对应的正是：先以代价 \(639\) 从第 1 行进入第 2 列，再向上经过数值 \(234\)。
继续按列推进到最后一列，得到
$$D^{(4)} = (994, 1144, 1255, 2211, 2222).$$
因此示例的最小值为
$$\min_r D^{(4)}_r = 994,$$
对应路径是 \(201 \to 96 \to 342 \to 234 \to 103 \to 18\)。
C++、Python 和 Java 三个实现都会先把 CSV 形式的矩阵读入一个二维数组，再维护一个表示“当前列最优代价”的一维动态规划向量。这个向量一开始就是第一列本身，因为第一列的任意一行都可以作为起点。
之后每处理一列，程序先把新列的值加到每一行上，形成“直接向右进入”的候选；然后做一次从上到下的松弛，再做一次从下到上的松弛。这两步与上面的数学推导完全对应。等最后一列处理完以后，向量中的最小值就是从左边界走到右边界的最小路径和。
每一列都只需要对行做三次线性遍历：一次初始化，一次向下扫描，一次向上扫描。因此对于 \(n \times n\) 矩阵，总时间复杂度是 \(O(n^2)\)。
额外工作内存是 \(O(n)\)，因为除输入矩阵外，算法只需要保存当前列的代价向量。对于题目的 \(80 \times 80\) 规模，这个方法完全足够，而且比把整个网格都交给通用最短路算法处理更直接、更轻量。
Дана квадратная матрица из положительных целых чисел. Допустимый путь может начинаться в любой строке первого столбца и заканчиваться в любой строке последнего столбца. Разрешены шаги вправо, вверх и вниз, но запрещены шаги влево. Нужно минимизировать сумму всех значений, по которым проходит путь.
Главная трудность по сравнению с более простыми задачами о движении только вправо и вниз состоит в том, что внутри одного столбца разрешены вертикальные перемещения. Поэтому лучший результат для клетки зависит не только от клетки слева, но и от того, в какую строку мы вошли в текущем столбце. Естественным состоянием динамики становится не отдельная клетка, а целый уже обработанный столбец.
Обозначим через \(M_{r,c}\) элемент матрицы в строке \(r\) и столбце \(c\), где \(0 \le r,c < n\). После обработки столбца \(c\) величина \(D^{(c)}_r\) означает минимальную сумму пути среди всех допустимых путей, заканчивающихся в клетке \((r,c)\). Тогда окончательный ответ равен
$$\min_{0 \le r < n} D^{(n-1)}_r.$$
В первом столбце никакого движения еще не было: каждая строка может быть выбрана стартовой. Поэтому начальное состояние имеет вид
$$D^{(0)}_r = M_{r,0} \qquad (0 \le r < n).$$
Именно эту инварианту сохраняют реализации: когда столбец \(c\) полностью обработан, вектор \(D^{(c)}\) содержит точные оптимальные стоимости достижения каждой строки этого столбца.
Зафиксируем столбец \(c \ge 1\) и предположим, что предыдущий вектор \(D^{(c-1)}\) уже известен. Любой путь, заканчивающийся в строке \(r\) нового столбца, обязан сначала войти в столбец \(c\) слева в некоторой строке \(k\). За это он платит \(D^{(c-1)}_k + M_{k,c}\), после чего движется по столбцу \(c\) вертикально до строки \(r\).
Поскольку все числа в матрице положительны, а шаги влево запрещены, оптимальный путь внутри одного столбца никогда не меняет вертикальное направление. Если бы он сначала шел вверх, а потом вниз, или наоборот, то какая-то строка этого столбца была бы посещена дважды. Такой обход имеет положительную стоимость и может быть удален.
Значит, вертикальная часть внутри одного столбца всегда монотонна, и мы получаем точную формулу
$$D^{(c)}_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right).$$
То есть для каждой возможной строки входа \(k\) мы берем лучший путь до предыдущего столбца в этой строке и прибавляем ровно те элементы нового столбца, которые лежат между строками \(k\) и \(r\).
Эта формула естественно распадается на два семейства кандидатов. Если \(k \le r\), путь входит в новый столбец в строке \(k\) и дальше идет только вниз. Его вклад равен
$$D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}.$$
Если \(k \ge r\), путь входит в строке \(k\) и затем идет только вверх. Тогда вклад равен
$$D^{(c-1)}_k + \sum_{t=r}^{k} M_{t,c}.$$
Реализации начинают с кандидата прямого шага вправо:
$$T_r = D^{(c-1)}_r + M_{r,c}.$$
После этого выполняется проход сверху вниз:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r-1} + M_{r,c}\bigr)\qquad (r=1,2,\dots,n-1).$$
После такого прохода уже учтены все чисто нисходящие варианты, то есть
$$T_r = \min_{0 \le k \le r}\left(D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}\right).$$
Затем выполняется второй проход снизу вверх:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r+1} + M_{r,c}\bigr)\qquad (r=n-2,n-3,\dots,0).$$
Когда этот проход завершен, получается точное равенство
$$T_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right)=D^{(c)}_r.$$
Следовательно, два прохода не приближают ответ, а полностью вычисляют минимум по всем возможным строкам входа.
Для примерной матрицы
$$\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}$$
первый столбец дает
$$D^{(0)} = (131, 201, 630, 537, 805).$$
В столбце 1 прямые переходы вправо дают
$$T = (804, 297, 1433, 1236, 1537).$$
Проход сверху вниз улучшает строку 2 и приводит к
$$T = (804, 297, 1100, 1236, 1537),$$
а проход снизу вверх уже ничего не меняет. Значит,
$$D^{(1)} = (804, 297, 1100, 1236, 1537).$$
Столбец 2 особенно хорошо показывает, зачем нужны оба направления. Прямой вектор равен
$$T = (1038, 639, 1846, 1733, 2061).$$
После прохода сверху вниз он становится
$$T = (1038, 639, 1385, 1733, 2061),$$
а затем проход снизу вверх улучшает первую строку до
$$D^{(2)} = (873, 639, 1385, 1733, 2061).$$
Это улучшение соответствует входу в столбец 2 по строке 1 со стоимостью \(639\), после чего выгодно подняться вверх через значение \(234\).
Если продолжить процедуру до последнего столбца, получится
$$D^{(4)} = (994, 1144, 1255, 2211, 2222).$$
Следовательно, минимум в примере равен
$$\min_r D^{(4)}_r = 994,$$
и достигается по пути \(201 \to 96 \to 342 \to 234 \to 103 \to 18\).
Реализации на C++, Python и Java считывают CSV-матрицу в двумерный массив и поддерживают одномерный вектор динамики для текущего столбца. В начале этот вектор равен первой колонке, потому что любая ее строка может служить стартовой позицией.
Для каждого следующего столбца программа сначала формирует кандидаты прямого шага вправо, добавляя новый элемент столбца к каждой строке. Затем выполняются две релаксации: одна сверху вниз и одна снизу вверх. Они в точности соответствуют двум монотонным случаям из вывода выше. После обработки последнего столбца минимальный элемент вектора и есть искомая минимальная сумма пути от левого края до правого.
Каждый новый столбец обрабатывается тремя линейными проходами по строкам: инициализация, проход сверху вниз и проход снизу вверх. Для матрицы размера \(n \times n\) это дает \(O(n)\) работы на столбец и \(O(n^2)\) времени в целом.
Дополнительная рабочая память равна \(O(n)\), поскольку помимо входной матрицы алгоритму нужен только вектор текущих стоимостей. Для задачи с размером \(80 \times 80\) этого более чем достаточно; при этом не требуется запускать общий алгоритм кратчайших путей на всем графе решетки.
لدينا مصفوفة مربعة من الأعداد الصحيحة الموجبة. يمكن لأي مسار صالح أن يبدأ من أي صف في العمود الأول وأن ينتهي في أي صف في العمود الأخير. الحركات المسموح بها هي إلى اليمين وإلى الأعلى وإلى الأسفل، لكن الحركة إلى اليسار ممنوعة. المطلوب هو تصغير مجموع جميع القيم التي يمر بها المسار.
الصعوبة الحقيقية مقارنة بمسائل الحركة إلى اليمين والأسفل فقط هي أن الحركة العمودية داخل العمود الواحد مسموحة هنا. لذلك فإن أفضل قيمة لخلية معينة لا تعتمد فقط على الجار الأيسر، بل تعتمد أيضًا على الصف الذي دخلنا منه إلى ذلك العمود. لهذا يكون الوضع الطبيعي في البرمجة الديناميكية هو عمود كامل بعد معالجته، لا خلية منفردة.
لنرمز إلى عنصر المصفوفة في الصف \(r\) والعمود \(c\) بالرمز \(M_{r,c}\)، حيث \(0 \le r,c < n\). وبعد الانتهاء من معالجة العمود \(c\)، نعرّف \(D^{(c)}_r\) على أنه أصغر مجموع مسار بين جميع المسارات الصالحة التي تنتهي عند الخلية \((r,c)\). وعندئذ يكون الجواب النهائي هو
$$\min_{0 \le r < n} D^{(n-1)}_r.$$
في العمود الأول لم تحدث أي حركة بعد، ولذلك يمكن اختيار أي صف كنقطة بداية. ومن ثم يكون الوضع الابتدائي ببساطة
$$D^{(0)}_r = M_{r,0} \qquad (0 \le r < n).$$
وهذه هي الثابتة التي تحافظ عليها التطبيقات: ما إن ينتهي العمود \(c\) حتى يحتوي المتجه \(D^{(c)}\) على الكلفة المثلى الدقيقة للوصول إلى كل صف من صفوف ذلك العمود.
لنثبت عمودًا \(c \ge 1\) ولنفترض أن المتجه السابق \(D^{(c-1)}\) معلوم. أي مسار ينتهي في الصف \(r\) من العمود الجديد لا بد أن يدخل العمود \(c\) من اليسار عبر صف ما \(k\). عند تلك اللحظة يدفع الكلفة \(D^{(c-1)}_k + M_{k,c}\)، ثم يتحرك رأسيًا داخل العمود \(c\) حتى يصل إلى الصف \(r\).
ولأن جميع عناصر المصفوفة موجبة، ولأن الحركة إلى اليسار ممنوعة، فإن المسار الأمثل داخل عمود واحد لا يغيّر اتجاهه الرأسي أبدًا. فإذا صعد ثم نزل، أو نزل ثم صعد، فهذا يعني أن صفًا من ذلك العمود قد زِير مرتين، أي نشأ التفاف ذو كلفة موجبة يمكن حذفه.
إذًا يكون الجزء الرأسي داخل العمود الواحد أحادي الاتجاه دائمًا، ونحصل على الصيغة الدقيقة
$$D^{(c)}_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right).$$
ومعنى ذلك أنه لكل صف دخول محتمل \(k\)، نأخذ أفضل كلفة للوصول إلى العمود السابق في ذلك الصف، ثم نضيف بالضبط القيم التي لا بد من المرور بها في العمود \(c\) بين الصفين \(k\) و\(r\).
تنقسم الصيغة السابقة طبيعيًا إلى نوعين من المرشحين. إذا كان \(k \le r\)، فإن المسار يدخل العمود الجديد عند الصف \(k\) ثم يتحرك إلى الأسفل فقط، وتكون مساهمته
$$D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}.$$
أما إذا كان \(k \ge r\)، فإنه يدخل عند الصف \(k\) ثم يتحرك إلى الأعلى فقط، وعندئذ تكون المساهمة
$$D^{(c-1)}_k + \sum_{t=r}^{k} M_{t,c}.$$
تبدأ التطبيقات ببناء مرشح الانتقال المباشر إلى اليمين:
$$T_r = D^{(c-1)}_r + M_{r,c}.$$
ثم تُجرى عملية مسح من الأعلى إلى الأسفل:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r-1} + M_{r,c}\bigr)\qquad (r=1,2,\dots,n-1).$$
بعد هذه الخطوة تكون جميع الاحتمالات التي تدخل من الأعلى ثم تتابع نزولًا قد أُخذت في الحسبان، ولذلك يصبح
$$T_r = \min_{0 \le k \le r}\left(D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}\right).$$
ثم تأتي عملية مسح ثانية من الأسفل إلى الأعلى:
$$T_r \leftarrow \min\bigl(T_r,\; T_{r+1} + M_{r,c}\bigr)\qquad (r=n-2,n-3,\dots,0).$$
وعند انتهاء المسح الثاني نحصل بالضبط على
$$T_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right)=D^{(c)}_r.$$
إذن فعمليتا المسح ليستا حيلة تقريبية، بل هما طريقة مضغوطة لحساب الحد الأدنى الحقيقي على جميع صفوف الدخول الممكنة.
بالنسبة إلى المصفوفة المثال
$$\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}$$
يعطينا العمود الأول
$$D^{(0)} = (131, 201, 630, 537, 805).$$
وفي العمود 1 تكون مرشحات الانتقال المباشر إلى اليمين هي
$$T = (804, 297, 1433, 1236, 1537).$$
ثم يحسن المسح النازل الصف الثاني إلى
$$T = (804, 297, 1100, 1236, 1537),$$
ولا يضيف المسح الصاعد أي تحسين جديد، ومن ثم نحصل على
$$D^{(1)} = (804, 297, 1100, 1236, 1537).$$
أما العمود 2 فهو يوضح لماذا نحتاج إلى الاتجاهين معًا. فالمتجه المباشر هو
$$T = (1038, 639, 1846, 1733, 2061).$$
وبعد المسح من الأعلى إلى الأسفل يصبح
$$T = (1038, 639, 1385, 1733, 2061),$$
ثم يأتي المسح من الأسفل إلى الأعلى ليحسن الصف الأول إلى
$$D^{(2)} = (873, 639, 1385, 1733, 2061).$$
ويحدث هذا التحسين لأن من الأفضل دخول العمود 2 عند الصف 1 بكلفة \(639\)، ثم الصعود عبر القيمة \(234\).
وعند متابعة العملية حتى العمود الأخير نحصل على
$$D^{(4)} = (994, 1144, 1255, 2211, 2222).$$
إذًا يكون الحد الأدنى في المثال هو
$$\min_r D^{(4)}_r = 994,$$
ويتحقق بواسطة المسار \(201 \to 96 \to 342 \to 234 \to 103 \to 18\).
تقرأ تطبيقات C++ وPython وJava المصفوفة بصيغة CSV داخل بنية ثنائية الأبعاد، ثم تحتفظ بمتجه برمجة ديناميكية أحادي البعد يمثل كلفة العمود الجاري. ويبدأ هذا المتجه بقيم العمود الأول نفسه، لأن أي صف فيه صالح كنقطة انطلاق.
ولكل عمود تالٍ، تبني الشيفرة أولًا مرشحات الدخول المباشر من اليسار بإضافة قيمة العمود الجديد إلى كل صف. بعد ذلك تنفذ مسحًا من الأعلى إلى الأسفل ثم مسحًا من الأسفل إلى الأعلى. وهاتان الخطوتان تطابقان تمامًا الحالتين الأحاديتين في الاشتقاق الرياضي أعلاه. وبعد إنهاء العمود الأخير، تكون أصغر قيمة في المتجه هي أصغر مجموع مسار من الحافة اليسرى إلى الحافة اليمنى.
يُعالَج كل عمود جديد بواسطة ثلاث تمريرات خطية على الصفوف: تمريرة تهيئة، ثم مسح نازل، ثم مسح صاعد. لذلك يكون الزمن الكلي لمصفوفة \(n \times n\) هو \(O(n^2)\).
أما الذاكرة العاملة الإضافية فهي \(O(n)\)، لأن الخوارزمية لا تحتاج، فوق مصفوفة الإدخال، إلا إلى متجه كلفة العمود الحالي. وبالنسبة إلى الحالة \(80 \times 80\) في المسألة، فإن هذا النهج سريع ومباشر، ويتجنب الكلفة الإضافية لتشغيل خوارزمية أقصر طريق عامة على كامل شبكة الخلايا.