The input is a 15-row triangle of positive integers. Starting at the apex, each move from row \(r\), column \(c\) may go only to row \(r+1\), column \(c\) or \(c+1\). The goal is to maximize the sum of the visited entries from the top to the base.
If the height is \(h\), a top-to-bottom route makes one binary choice in each of the first \(h-1\) rows, so there are \(2^{h-1}\) possible routes. For Problem 18, \(h=15\), hence \(2^{14}=16384\) candidate paths. The implementations still use dynamic programming, because many different routes share the same suffixes and the optimum can be recovered without enumerating any complete path.
Let \(a_{r,c}\) be the entry in row \(r\), column \(c\), where \(0\le r\le h-1\) and \(0\le c\le r\). A valid path is a sequence of positions beginning at \((0,0)\) and ending somewhere on the last row, with each step changing the column by either \(0\) or \(1\). The central idea is to treat every cell as the start of a smaller maximum-path problem.
Define \(F(r,c)\) to be the maximum sum obtainable from cell \((r,c)\) down to the base. Once the path has reached \((r,c)\), everything above it is already fixed, so the only remaining question is the best route through the subtriangle rooted at that cell. This is the exact overlapping-subproblem structure that the implementations exploit.
At the bottom row there is no further choice, so the boundary condition is immediate:
$$F(h-1,c)=a_{h-1,c} \qquad (0\le c\le h-1).$$
From \((r,c)\) there are exactly two legal next positions, namely \((r+1,c)\) and \((r+1,c+1)\). Therefore every optimal path from \((r,c)\) must take the better of those two suffixes, which gives the recurrence
$$F(r,c)=a_{r,c}+\max\bigl(F(r+1,c),\,F(r+1,c+1)\bigr).$$
This is not a heuristic. It follows directly from the rules of the problem: any admissible path must choose one of those two children, and after that first step the remaining task is again a maximum-path problem of the same form.
The recurrence for row \(r\) depends only on row \(r+1\), so the values can be computed from the bottom upward. Start with the last row, collapse the row above it, then keep moving upward until only the apex remains. A downward induction on \(r\) proves correctness: if the row below already stores the exact values \(F(r+1,\cdot)\), then one application of the recurrence produces the exact values \(F(r,\cdot)\).
Equivalently, after row \(r\) has been processed, the working row satisfies the invariant that its \(c\)-th entry equals the best possible sum from \((r,c)\) to the base. When the process reaches \(r=0\), the lone remaining value is \(F(0,0)\), the required maximum total.
The sample triangle used as a checkpoint in the implementations has rows \((3)\), \((7,4)\), \((2,4,6)\), and \((8,5,9,3)\).
Begin with the last row \((8,5,9,3)\). Collapsing the row above gives
$$(2+\max(8,5),\ 4+\max(5,9),\ 6+\max(9,3))=(10,13,15).$$
Collapsing the next row gives
$$(7+\max(10,13),\ 4+\max(13,15))=(20,19).$$
Finally the apex becomes
$$3+\max(20,19)=23.$$
So the maximum path sum is \(23\). The full 15-row instance is solved by exactly the same bottom-up reduction, only with more rows.
The C++, Python, and Java implementations store the 15-row triangle directly and copy the last row into a one-dimensional working array. At that moment, the working array already equals the correct values of \(F(h-1,c)\) for the base row.
The implementations then iterate from the second-last row to the top. For each position they replace the current working entry by the current triangle value plus the larger of its two child values from the row below. Only one row of memory is needed, because row \(r\) depends exclusively on row \(r+1\).
The in-place update order is safe: when a position is updated, the two child values it needs still represent the row below. After a full pass over row \(r\), the first \(r+1\) entries of the working array are exactly the values \(F(r,0),F(r,1),\dots,F(r,r)\). All three implementations also verify the 4-row sample whose correct answer is \(23\).
A triangle of height \(h\) contains
$$N=\frac{h(h+1)}{2}$$
entries. The dynamic program touches each non-base cell once, so the running time is \(O(N)\), equivalently \(O(h^2)\). The extra memory is \(O(h)\), because only one working row is stored.
For Problem 18 specifically, \(h=15\) and \(N=120\). After copying the bottom row, the reduction phase performs \(1+2+\cdots+14=105\) updates, which is far smaller than exploring all \(2^{14}=16384\) complete routes one by one.
Die Eingabe ist ein Zahlendreieck mit 15 Zeilen. Ausgehend von der Spitze darf man von Zeile \(r\), Spalte \(c\) nur nach \((r+1,c)\) oder \((r+1,c+1)\) gehen. Gesucht ist die größtmögliche Summe aller besuchten Einträge vom oberen Wert bis zur Basis.
Hat das Dreieck die Höhe \(h\), dann enthält jeder vollständige Weg in den ersten \(h-1\) Zeilen genau eine binäre Entscheidung pro Zeile, also insgesamt \(2^{h-1}\) mögliche Wege. Für Problem 18 ist \(h=15\), also gibt es \(2^{14}=16384\) Kandidaten. Die Implementierungen verwenden trotzdem dynamische Programmierung, weil viele dieser Wege dieselben Restdreiecke teilen und man das Optimum ohne vollständige Enumeration bestimmen kann.
Bezeichne den Eintrag in Zeile \(r\), Spalte \(c\) mit \(a_{r,c}\), wobei \(0\le r\le h-1\) und \(0\le c\le r\) gilt. Ein zulässiger Weg beginnt bei \((0,0)\) und endet in der letzten Zeile; bei jedem Schritt erhöht sich die Spalte um \(0\) oder \(1\). Der Kern der Lösung ist, jede Zelle als Startpunkt eines kleineren Maximalweg-Problems zu betrachten.
Definiere \(F(r,c)\) als die maximal erreichbare Summe von der Zelle \((r,c)\) bis zur Basis. Sobald ein Weg \((r,c)\) erreicht hat, ist alles oberhalb bereits festgelegt; offen bleibt nur noch, welcher Weg durch das untere Restdreieck optimal ist. Genau diese überlappenden Teilprobleme nutzen die Implementierungen aus.
In der letzten Zeile gibt es keine Wahl mehr, daher ist die Randbedingung sofort klar:
$$F(h-1,c)=a_{h-1,c} \qquad (0\le c\le h-1).$$
Von \((r,c)\) aus sind genau zwei nächste Positionen erlaubt, nämlich \((r+1,c)\) und \((r+1,c+1)\). Daher muss jeder optimale Weg ab \((r,c)\) den besseren dieser beiden Folgezustände wählen. Das liefert die Rekurrenz
$$F(r,c)=a_{r,c}+\max\bigl(F(r+1,c),\,F(r+1,c+1)\bigr).$$
Diese Formel ist keine Näherung, sondern eine direkte Konsequenz der Aufgabenregel: Jeder zulässige Weg beginnt mit genau einem dieser beiden Kinder, und danach bleibt wieder ein Problem derselben Art übrig.
Die Rekurrenz für Zeile \(r\) hängt nur von Zeile \(r+1\) ab. Deshalb kann man die Werte von unten nach oben ausrechnen: zuerst die letzte Zeile, dann die vorletzte, dann die nächste darüber, bis nur noch die Spitze übrig bleibt. Die Korrektheit folgt per absteigender Induktion über \(r\): Wenn die darunterliegende Zeile bereits die exakten Werte \(F(r+1,\cdot)\) enthält, erzeugt ein Anwendungsschritt der Rekurrenz die exakten Werte \(F(r,\cdot)\).
Äquivalent dazu gilt als Invariante: Nachdem Zeile \(r\) verarbeitet wurde, steht an Position \(c\) der Arbeitszeile genau die beste Summe von \((r,c)\) bis zur Basis. Wenn schließlich \(r=0\) erreicht ist, bleibt nur \(F(0,0)\) übrig, also die gesuchte Maximalsumme.
Das in den Implementierungen verwendete Prüfbeispiel hat die Zeilen \((3)\), \((7,4)\), \((2,4,6)\) und \((8,5,9,3)\).
Man beginnt mit der letzten Zeile \((8,5,9,3)\). Die darüberliegende Zeile wird zu
$$(2+\max(8,5),\ 4+\max(5,9),\ 6+\max(9,3))=(10,13,15).$$
Die nächste Reduktion ergibt
$$(7+\max(10,13),\ 4+\max(13,15))=(20,19).$$
Für die Spitze bleibt dann
$$3+\max(20,19)=23.$$
Damit ist die maximale Pfadsumme \(23\). Für das eigentliche 15-Zeilen-Dreieck läuft exakt dieselbe Reduktion, nur über mehr Zeilen.
Die C++-, Python- und Java-Implementierungen hinterlegen das 15-zeilige Dreieck direkt und kopieren zunächst die letzte Zeile in ein eindimensionales Arbeitsarray. In diesem Moment enthält das Array bereits die korrekten Werte \(F(h-1,c)\) der Basis.
Anschließend laufen die Implementierungen von der vorletzten Zeile bis zur Spitze. Für jede Position wird der aktuelle Arbeitswert durch „aktueller Dreieckseintrag plus Maximum der beiden Kinder“ ersetzt. Mehr als eine Zeile Zusatzspeicher ist nicht nötig, weil Zeile \(r\) ausschließlich von Zeile \(r+1\) abhängt.
Die In-Place-Reihenfolge ist sicher: Beim Überschreiben einer Position repräsentieren die beiden benötigten Kinderwerte noch immer die darunterliegende Zeile. Nach einem vollständigen Durchlauf über Zeile \(r\) sind die ersten \(r+1\) Einträge des Arbeitsarrays genau \(F(r,0),F(r,1),\dots,F(r,r)\). Alle drei Implementierungen prüfen außerdem das 4-Zeilen-Beispiel mit dem korrekten Ergebnis \(23\).
Ein Dreieck der Höhe \(h\) besitzt
$$N=\frac{h(h+1)}{2}$$
Einträge. Das dynamische Programm verarbeitet jede Nicht-Basis-Zelle genau einmal, also beträgt die Laufzeit \(O(N)\), äquivalent \(O(h^2)\). Der zusätzliche Speicherbedarf ist \(O(h)\), weil nur eine Arbeitszeile gespeichert wird.
Für Problem 18 gilt konkret \(h=15\) und \(N=120\). Nach dem Kopieren der Basiszeile werden in der Reduktionsphase \(1+2+\cdots+14=105\) Aktualisierungen ausgeführt. Das ist deutlich kleiner als eine vollständige Betrachtung aller \(2^{14}=16384\) Wege.
Girdi, 15 satırlı bir sayı üçgenidir. Tepe noktasından başlanır ve \(r\). satırın \(c\). sütunundaki bir hücreden yalnızca \((r+1,c)\) ya da \((r+1,c+1)\) konumuna geçilebilir. Amaç, tepeden tabana inerken ziyaret edilen sayıların toplamını en büyük yapmaktır.
Üçgenin yüksekliği \(h\) ise, tam bir yol ilk \(h-1\) satırın her birinde bir ikili seçim yapar; dolayısıyla toplam yol sayısı \(2^{h-1}\) olur. Problem 18 için \(h=15\) olduğundan \(2^{14}=16384\) aday yol vardır. Buna rağmen uygulamalar dinamik programlama kullanır; çünkü farklı yolların büyük kısmı aynı alt üçgenleri paylaşır ve optimum değer tam yolları tek tek gezmeden elde edilebilir.
\(a_{r,c}\) ile \(r\). satırın \(c\). sütunundaki değeri gösterelim; burada \(0\le r\le h-1\) ve \(0\le c\le r\) olsun. Geçerli bir yol \((0,0)\) noktasından başlar, son satıra ulaşır ve her adımda sütun numarasını ya sabit tutar ya da 1 artırır. Çözümün ana fikri, her hücreyi daha küçük bir maksimum-yol probleminin başlangıcı olarak ele almaktır.
\(F(r,c)\), \((r,c)\) hücresinden tabana kadar elde edilebilecek en büyük toplam olsun. Yol bir kez \((r,c)\) noktasına geldiğinde, onun üstünde kalan kısım artık sabittir; geriye sadece bu hücrenin altındaki alt üçgende en iyi yolun hangisi olduğunu bulmak kalır. Uygulamaların kullandığı örtüşen alt problem yapısı tam olarak budur.
Son satırda artık seçim kalmaz; dolayısıyla sınır koşulu doğrudan
$$F(h-1,c)=a_{h-1,c} \qquad (0\le c\le h-1)$$
şeklindedir.
\((r,c)\) hücresinden yalnızca iki sonraki konuma gidilebilir: \((r+1,c)\) ve \((r+1,c+1)\). Bu nedenle \((r,c)\) noktasından başlayan her optimal yol, bu iki devam yolundan daha iyisini seçmek zorundadır. Böylece
$$F(r,c)=a_{r,c}+\max\bigl(F(r+1,c),\,F(r+1,c+1)\bigr)$$
yinelemesi elde edilir. Bu bir sezgisel kural değildir; doğrudan problem tanımından gelir. Her geçerli yol önce bu iki çocuktan birine iner, sonra da aynı türden daha küçük bir problem kalır.
\(r\). satırdaki değer, yalnızca \(r+1\). satıra bağlıdır. Bu yüzden hesaplama aşağıdan yukarı yapılabilir: önce son satır, sonra bir üst satır, sonra onun üstü ve en son tepe. Doğruluk, \(r\) üzerinde aşağı doğru tümevarımla gelir: alttaki satır zaten tam olarak \(F(r+1,\cdot)\) değerlerini içeriyorsa, yinelemeyi bir kez uygulamak \(F(r,\cdot)\) değerlerini verir.
Aynı fikir bir değişmez olarak da ifade edilebilir: \(r\). satır işlendiğinde çalışma satırının \(c\). elemanı, \((r,c)\) hücresinden tabana kadar olan en iyi toplamdır. Süreç \(r=0\)'a ulaştığında geriye tek bir sayı kalır; bu da istenen maksimum toplam olan \(F(0,0)\)'dır.
Uygulamaların kontrol amacıyla kullandığı örnek üçgenin satırları \((3)\), \((7,4)\), \((2,4,6)\) ve \((8,5,9,3)\) şeklindedir.
İşe son satır olan \((8,5,9,3)\) ile başlanır. Bir üst satır şu hale gelir:
$$(2+\max(8,5),\ 4+\max(5,9),\ 6+\max(9,3))=(10,13,15).$$
Bir sonraki küçültme:
$$(7+\max(10,13),\ 4+\max(13,15))=(20,19).$$
Son olarak tepe değeri
$$3+\max(20,19)=23$$
olur. Böylece maksimum yol toplamı \(23\) bulunur. Gerçek 15 satırlı veri için yapılan işlem de aynıdır; yalnızca daha fazla satır küçültülür.
C++, Python ve Java uygulamaları 15 satırlı üçgeni doğrudan içerir ve önce son satırı tek boyutlu bir çalışma dizisine kopyalar. Bu anda çalışma dizisi zaten taban için doğru \(F(h-1,c)\) değerlerini taşır.
Daha sonra uygulamalar sondan bir önceki satırdan başlayıp tepeye kadar ilerler. Her konum için çalışma dizisindeki ilgili değer, o hücrenin sayısı ile alttaki iki çocuktan büyüğünün toplamı olacak şekilde güncellenir. Yalnızca tek bir satırlık ek bellek yeterlidir; çünkü \(r\). satır yalnızca \(r+1\). satıra bakar.
Yerinde güncelleme sırası güvenlidir: bir konum güncellenirken ihtiyaç duyulan iki çocuk değeri hâlâ alt satırı temsil eder. \(r\). satır üzerindeki geçiş tamamlandığında çalışma dizisinin ilk \(r+1\) elemanı tam olarak \(F(r,0),F(r,1),\dots,F(r,r)\) olur. Üç uygulama da ayrıca 4 satırlı örneğin cevabının \(23\) olduğunu doğrular.
Yüksekliği \(h\) olan bir üçgende toplam
$$N=\frac{h(h+1)}{2}$$
adet hücre vardır. Dinamik programlama taban dışındaki her hücreye bir kez dokunur; dolayısıyla çalışma süresi \(O(N)\), yani eşdeğer olarak \(O(h^2)\) olur. Ek bellek maliyeti ise yalnızca tek çalışma satırı tutulduğu için \(O(h)\)'dir.
Problem 18 özelinde \(h=15\) ve \(N=120\)'dir. Taban satırı kopyalandıktan sonra küçültme aşaması \(1+2+\cdots+14=105\) güncelleme yapar. Bu sayı, tüm \(2^{14}=16384\) tam yolu tek tek değerlendirmekten çok daha küçüktür.
La entrada es un triángulo numérico de 15 filas. Desde el vértice, un movimiento desde la fila \(r\), columna \(c\), solo puede bajar a \((r+1,c)\) o a \((r+1,c+1)\). El objetivo es maximizar la suma de los valores visitados desde la cima hasta la base.
Si la altura del triángulo es \(h\), un recorrido completo hace una elección binaria en cada una de las primeras \(h-1\) filas, así que existen \(2^{h-1}\) rutas posibles. En el Problema 18, \(h=15\), por lo que hay \(2^{14}=16384\) caminos candidatos. Aun así, las implementaciones usan programación dinámica, porque muchas rutas comparten exactamente los mismos sufijos y el óptimo puede recuperarse sin enumerar ningún camino completo.
Sea \(a_{r,c}\) el valor situado en la fila \(r\), columna \(c\), con \(0\le r\le h-1\) y \(0\le c\le r\). Un camino válido empieza en \((0,0)\), termina en la última fila y en cada paso mantiene la columna o la incrementa en 1. La idea central consiste en considerar cada casilla como el origen de un problema más pequeño del mismo tipo.
Definimos \(F(r,c)\) como la suma máxima que puede obtenerse desde la casilla \((r,c)\) hasta la base. Una vez que el recorrido ha llegado a \((r,c)\), todo lo anterior ya está fijado; lo único que queda por decidir es cuál es la mejor ruta dentro del subtriángulo que cuelga de esa casilla. Esa es exactamente la estructura de subproblemas superpuestos que explotan las implementaciones.
En la última fila no queda ninguna elección, así que la condición de borde es inmediata:
$$F(h-1,c)=a_{h-1,c} \qquad (0\le c\le h-1).$$
Desde \((r,c)\) solo existen dos posiciones siguientes legales: \((r+1,c)\) y \((r+1,c+1)\). Por tanto, cualquier camino óptimo que salga de \((r,c)\) debe tomar el mejor de esos dos sufijos, lo que produce la recurrencia
$$F(r,c)=a_{r,c}+\max\bigl(F(r+1,c),\,F(r+1,c+1)\bigr).$$
No es una regla heurística. Sale directamente de la definición del problema: todo camino admisible empieza bajando a uno de esos dos hijos y, después de ese primer paso, vuelve a quedar un problema de suma máxima del mismo tipo.
La fórmula de la fila \(r\) depende solo de la fila \(r+1\), así que los valores pueden calcularse de abajo hacia arriba. Se empieza por la última fila, luego se colapsa la anterior, después la siguiente, y así sucesivamente hasta dejar un único valor en el vértice. La corrección se demuestra por inducción descendente sobre \(r\): si la fila inferior ya contiene los valores exactos \(F(r+1,\cdot)\), entonces una sola aplicación de la recurrencia produce los valores exactos \(F(r,\cdot)\).
La misma idea puede expresarse como un invariante: después de procesar la fila \(r\), la entrada \(c\) de la fila de trabajo coincide con la mejor suma posible desde \((r,c)\) hasta la base. Cuando el proceso llega a \(r=0\), el valor restante es \(F(0,0)\), es decir, la respuesta buscada.
El triángulo de prueba usado en las implementaciones tiene las filas \((3)\), \((7,4)\), \((2,4,6)\) y \((8,5,9,3)\).
Se empieza con la última fila \((8,5,9,3)\). Al colapsar la fila superior se obtiene
$$(2+\max(8,5),\ 4+\max(5,9),\ 6+\max(9,3))=(10,13,15).$$
La siguiente reducción produce
$$(7+\max(10,13),\ 4+\max(13,15))=(20,19).$$
Por último, el vértice queda en
$$3+\max(20,19)=23.$$
Así, la suma máxima del camino es \(23\). La instancia real de 15 filas se resuelve con exactamente la misma reducción ascendente.
Las implementaciones en C++, Python y Java incorporan directamente el triángulo de 15 filas y copian la última fila en un arreglo de trabajo unidimensional. En ese instante, dicho arreglo ya coincide con los valores correctos \(F(h-1,c)\) de la base.
Después recorren las filas desde la penúltima hasta la cima. En cada posición, reemplazan la entrada de trabajo por “valor actual del triángulo más el máximo de sus dos hijos”. Solo hace falta una fila de memoria adicional, porque la fila \(r\) depende exclusivamente de la fila \(r+1\).
El orden de actualización in situ es seguro: cuando se actualiza una posición, los dos valores hijos que necesita siguen representando la fila inferior. Tras completar la fila \(r\), las primeras \(r+1\) entradas del arreglo de trabajo son exactamente \(F(r,0),F(r,1),\dots,F(r,r)\). Las tres implementaciones también verifican el ejemplo de 4 filas cuya respuesta correcta es \(23\).
Un triángulo de altura \(h\) contiene
$$N=\frac{h(h+1)}{2}$$
entradas. El programa dinámico visita una vez cada celda que no pertenece a la base, así que el tiempo es \(O(N)\), o de forma equivalente \(O(h^2)\). La memoria extra es \(O(h)\), ya que solo se guarda una fila de trabajo.
Para el Problema 18 en particular, \(h=15\) y \(N=120\). Tras copiar la última fila, la fase de reducción realiza \(1+2+\cdots+14=105\) actualizaciones, mucho menos que evaluar una por una las \(2^{14}=16384\) rutas completas.
输入是一个 15 行的数字三角形。从顶点出发，若当前位置在第 \(r\) 行第 \(c\) 列，那么下一步只能走到 \((r+1,c)\) 或 \((r+1,c+1)\)。目标是让从顶部到底部所经过数字的总和尽可能大。
如果三角形高度为 \(h\)，那么一条完整路径会在前 \(h-1\) 行各做一次二选一，因此一共存在 \(2^{h-1}\) 条候选路径。对 Problem 18 而言，\(h=15\)，所以共有 \(2^{14}=16384\) 条路径。即便如此，三个实现仍然采用动态规划，因为大量不同路径会共享同一个后缀子三角形，最优值可以在不枚举完整路径的前提下直接合并出来。
记第 \(r\) 行第 \(c\) 列的数字为 \(a_{r,c}\)，其中 \(0\le r\le h-1\) 且 \(0\le c\le r\)。一条合法路径从 \((0,0)\) 出发，到达最后一行，并且每走一步，列号只能保持不变或增加 1。整个方法的核心，是把每一个格子都看成一个更小的“最大路径和”问题的起点。
定义 \(F(r,c)\) 为从格子 \((r,c)\) 出发一直走到底边时能够取得的最大总和。一旦路径已经到达 \((r,c)\)，上面的部分就已经固定了，剩下要决定的只有这个格子下面那块子三角形中的最优走法。这正是三个实现所利用的重叠子问题结构。
在最底行已经没有后续选择，因此边界条件立刻得到：
$$F(h-1,c)=a_{h-1,c} \qquad (0\le c\le h-1).$$
从 \((r,c)\) 出发，下一步只有两个合法位置：\((r+1,c)\) 和 \((r+1,c+1)\)。因此，从 \((r,c)\) 开始的最优路径一定要在这两个子问题中选较大的那个，于是得到递推关系
$$F(r,c)=a_{r,c}+\max\bigl(F(r+1,c),\,F(r+1,c+1)\bigr).$$
这不是经验公式，而是由题目的移动规则强制得到的。任何合法路径都必须先走向这两个孩子之一，而迈出第一步之后，剩下的部分仍然是同一种最大路径和问题。
第 \(r\) 行的值只依赖于第 \(r+1\) 行，因此最自然的做法是从底部往上算。先把最后一行作为已知值，再合并倒数第二行，然后继续向上，直到顶部只剩下一个数。正确性可以用对 \(r\) 的向下归纳来说明：如果下一行已经准确存储了 \(F(r+1,\cdot)\)，那么把递推式应用到这一行，就会得到准确的 \(F(r,\cdot)\)。
也可以把它写成一个实现不变量：当第 \(r\) 行处理完成后，工作行中第 \(c\) 个位置存放的正是从 \((r,c)\) 到底边的最优总和。等处理到 \(r=0\) 时，唯一剩下的数就是 \(F(0,0)\)，也就是题目要求的最大总和。
三个实现都带有同一个校验三角形，其四行分别是 \((3)\)、\((7,4)\)、\((2,4,6)\) 和 \((8,5,9,3)\)。
先从最后一行 \((8,5,9,3)\) 开始。向上合并一行后得到
$$(2+\max(8,5),\ 4+\max(5,9),\ 6+\max(9,3))=(10,13,15).$$
再向上合并一行，得到
$$(7+\max(10,13),\ 4+\max(13,15))=(20,19).$$
最后顶部变成
$$3+\max(20,19)=23.$$
因此这个示例的最大路径和是 \(23\)。真正的 15 行输入只是把同样的自底向上压缩过程继续应用到更大的三角形上。
C++、Python 和 Java 的实现都会直接保存题目的 15 行三角形，并先把最后一行复制到一个一维工作数组中。此时这个数组已经等于底边上的正确值 \(F(h-1,c)\)。
随后，三个实现都从倒数第二行开始一路向上。对于当前行中的每个位置，都把工作数组中的对应值改写成“当前数字加上两个孩子中的较大者”。因为第 \(r\) 行只依赖第 \(r+1\) 行，所以只保留一行状态就足够了。
这种原地更新顺序是安全的：当某个位置被改写时，它所需要的两个孩子值仍然代表下一行。整行处理结束后，工作数组的前 \(r+1\) 个位置就恰好是 \(F(r,0),F(r,1),\dots,F(r,r)\)。此外，三个实现都会先验证 4 行样例的正确答案确实是 \(23\)。
高度为 \(h\) 的三角形一共有
$$N=\frac{h(h+1)}{2}$$
个数字。动态规划会对每个非底边格子处理一次，因此时间复杂度是 \(O(N)\)，也就是等价的 \(O(h^2)\)。额外空间复杂度为 \(O(h)\)，因为只需要保存一行工作状态。
对 Problem 18 来说，\(h=15\)，\(N=120\)。复制完底边后，向上压缩阶段会执行 \(1+2+\cdots+14=105\) 次状态更新，这比逐条考察 \(2^{14}=16384\) 条完整路径要小得多。
На вход дан числовой треугольник из 15 строк. Из вершины можно двигаться вниз только к одному из двух соседних элементов следующей строки: из позиции \((r,c)\) разрешены переходы лишь в \((r+1,c)\) и \((r+1,c+1)\). Нужно максимизировать сумму чисел на пути от вершины до основания.
Если высота треугольника равна \(h\), то полный путь делает по одному бинарному выбору в каждой из первых \(h-1\) строк, а значит существует \(2^{h-1}\) возможных маршрутов. В Problem 18 имеем \(h=15\), то есть \(2^{14}=16384\) кандидата. Тем не менее реализации используют динамическое программирование, потому что многие разные пути имеют общий хвост, и оптимум можно получить без перебора каждого полного маршрута.
Обозначим через \(a_{r,c}\) число в строке \(r\) и позиции \(c\), где \(0\le r\le h-1\) и \(0\le c\le r\). Допустимый путь начинается в \((0,0)\), заканчивается в последней строке и на каждом шаге либо сохраняет номер столбца, либо увеличивает его на 1. Главная идея состоит в том, чтобы рассматривать каждую клетку как начало меньшей задачи того же типа.
Пусть \(F(r,c)\) обозначает максимальную сумму, которую можно получить, стартуя из клетки \((r,c)\) и спускаясь до основания. Как только путь уже пришел в \((r,c)\), верхняя часть маршрута больше не имеет значения; остается только выбрать лучший путь в под-треугольнике под этой клеткой. Именно такая структура перекрывающихся подзадач и используется в реализациях.
В последней строке выбора больше нет, поэтому граничное условие сразу имеет вид
$$F(h-1,c)=a_{h-1,c} \qquad (0\le c\le h-1).$$
Из клетки \((r,c)\) можно перейти только в две позиции: \((r+1,c)\) и \((r+1,c+1)\). Значит, любой оптимальный путь из \((r,c)\) обязан выбрать лучший из двух возможных хвостов, и потому
$$F(r,c)=a_{r,c}+\max\bigl(F(r+1,c),\,F(r+1,c+1)\bigr).$$
Это не эвристика, а прямое следствие определения задачи. Каждый допустимый маршрут сначала идет к одному из двух потомков, а затем перед нами снова остается задача о максимальной сумме по меньшему треугольнику.
Значение в строке \(r\) зависит только от строки \(r+1\), поэтому удобно считать снизу вверх. Сначала известна последняя строка, затем она поглощает предпоследнюю, затем следующую и так далее, пока не останется одна вершина. Корректность доказывается нисходящей индукцией по \(r\): если строка ниже уже содержит точные значения \(F(r+1,\cdot)\), то одно применение рекуррентной формулы дает точные значения \(F(r,\cdot)\).
То же самое можно выразить через инвариант: после обработки строки \(r\) ее \(c\)-й рабочий элемент равен наилучшей сумме от \((r,c)\) до основания. Когда процесс доходит до \(r=0\), единственное оставшееся число есть \(F(0,0)\), то есть искомый максимум.
Во всех реализациях используется один и тот же контрольный пример со строками \((3)\), \((7,4)\), \((2,4,6)\) и \((8,5,9,3)\).
Начинаем с нижней строки \((8,5,9,3)\). Свертка строки выше дает
$$(2+\max(8,5),\ 4+\max(5,9),\ 6+\max(9,3))=(10,13,15).$$
Следующая свертка дает
$$(7+\max(10,13),\ 4+\max(13,15))=(20,19).$$
Наконец, вершина превращается в
$$3+\max(20,19)=23.$$
Следовательно, максимальная сумма пути равна \(23\). Реальный 15-строчный вход решается абсолютно тем же методом, только с большим числом шагов свертки.
Реализации на C++, Python и Java напрямую задают 15-строчный треугольник и сначала копируют последнюю строку в одномерный рабочий массив. В этот момент массив уже совпадает с правильными значениями \(F(h-1,c)\) на основании.
После этого программы идут от предпоследней строки к вершине. Для каждой позиции рабочее значение заменяется на сумму текущего числа и большего из двух дочерних значений. Дополнительной памяти на всю таблицу не нужно, потому что строка \(r\) зависит только от строки \(r+1\).
Порядок обновления на месте корректен: когда очередная позиция пересчитывается, оба нужных дочерних значения еще представляют нижнюю строку. После полного прохода по строке \(r\) первые \(r+1\) элементов рабочего массива равны \(F(r,0),F(r,1),\dots,F(r,r)\). Кроме того, все три реализации предварительно проверяют контрольный пример, для которого ответ равен \(23\).
Треугольник высоты \(h\) содержит
$$N=\frac{h(h+1)}{2}$$
чисел. Динамическая программа обрабатывает каждую небазовую клетку ровно один раз, поэтому время работы равно \(O(N)\), или, что то же самое, \(O(h^2)\). Дополнительная память равна \(O(h)\), так как хранится только одна рабочая строка.
В Problem 18 конкретно \(h=15\) и \(N=120\). После копирования нижней строки фаза свертки выполняет \(1+2+\cdots+14=105\) обновлений, что намного меньше полного перебора всех \(2^{14}=16384\) маршрутов.
المدخل هو مثلث أعداد مكوَّن من 15 صفًا. بدءًا من القمة، إذا كنا في الموضع \((r,c)\) فلا يسمح لنا إلا بالنزول إلى \((r+1,c)\) أو \((r+1,c+1)\). الهدف هو تعظيم مجموع القيم التي نزورها من أعلى المثلث إلى قاعدته.
إذا كان ارتفاع المثلث هو \(h\)، فإن كل مسار كامل يقوم باختيار ثنائي واحد في كل صف من الصفوف \(h-1\) الأولى، ولذلك يوجد \(2^{h-1}\) مسارًا ممكنًا. في Problem 18 لدينا \(h=15\)، أي \(2^{14}=16384\) مسارًا مرشحًا. ومع ذلك تستخدم التطبيقات البرمجة الديناميكية، لأن كثيرًا من المسارات المختلفة تشترك في الذيل نفسه، ويمكن استخراج الحل الأمثل من دون تعداد كل مسار كامل على حدة.
لنرمز إلى قيمة الخانة الموجودة في الصف \(r\) والعمود \(c\) بالرمز \(a_{r,c}\)، حيث \(0\le r\le h-1\) و\(0\le c\le r\). المسار الصحيح يبدأ من \((0,0)\)، وينتهي في الصف الأخير، وفي كل خطوة يبقي رقم العمود كما هو أو يزيده بمقدار 1. الفكرة الأساسية هي أن نعتبر كل خلية بداية لمسألة أصغر من النوع نفسه.
نعرّف \(F(r,c)\) بأنه أكبر مجموع يمكن الحصول عليه إذا بدأنا من الخلية \((r,c)\) ونزلنا حتى القاعدة. ما إن يصل المسار إلى \((r,c)\)، يصبح الجزء الأعلى ثابتًا، ولا يبقى إلا تحديد أفضل طريق داخل المثلث الفرعي الواقع تحت هذه الخلية. هذه هي بالضبط بنية المسائل الفرعية المتداخلة التي تستغلها التطبيقات.
في الصف الأخير لا يبقى أي اختيار، ولذلك يكون شرط البداية واضحًا مباشرة:
$$F(h-1,c)=a_{h-1,c} \qquad (0\le c\le h-1).$$
من الموضع \((r,c)\) يوجد انتقالان قانونيان فقط: إلى \((r+1,c)\) أو إلى \((r+1,c+1)\). لذلك فإن أي مسار أمثل يبدأ من \((r,c)\) لا بد أن يختار الأفضل من هذين الامتدادين، ومن ثم نحصل على العلاقة
$$F(r,c)=a_{r,c}+\max\bigl(F(r+1,c),\,F(r+1,c+1)\bigr).$$
هذه ليست قاعدة حدسية، بل نتيجة مباشرة لتعريف المسألة. فكل مسار مسموح به يجب أن يهبط أولًا إلى أحد هذين الابنين، وبعد تلك الخطوة الأولى تبقى لدينا مرة أخرى مسألة مجموع أعظمي من النوع نفسه.
قيمة الصف \(r\) تعتمد فقط على الصف \(r+1\)، ولذلك يمكن حساب كل شيء بدءًا من القاعدة ثم الصعود تدريجيًا. نبدأ بالصف الأخير، ثم ندمج الصف الذي فوقه، ثم الذي فوقه، إلى أن لا يبقى إلا عنصر القمة. وتأتي الصحة من استقراء تنازلي على \(r\): إذا كان الصف الأسفل يحتوي بالفعل على القيم الصحيحة \(F(r+1,\cdot)\)، فإن تطبيق العلاقة العودية مرة واحدة يعطي القيم الصحيحة \(F(r,\cdot)\).
ويمكن صياغة الفكرة نفسها على شكل ثابت حلقي: بعد معالجة الصف \(r\)، تكون الخانة رقم \(c\) في صف العمل مساوية لأفضل مجموع ممكن من \((r,c)\) إلى القاعدة. وعندما نصل إلى \(r=0\)، تكون القيمة الوحيدة المتبقية هي \(F(0,0)\)، أي الجواب المطلوب.
هناك مثلث صغير تستخدمه التطبيقات الثلاثة للاختبار، وصفوفه هي \((3)\)، ثم \((7,4)\)، ثم \((2,4,6)\)، ثم \((8,5,9,3)\).
نبدأ من الصف الأخير \((8,5,9,3)\). وعند دمج الصف الذي فوقه نحصل على
$$(2+\max(8,5),\ 4+\max(5,9),\ 6+\max(9,3))=(10,13,15).$$
ثم تكون الخطوة التالية
$$(7+\max(10,13),\ 4+\max(13,15))=(20,19).$$
وفي النهاية تصبح القمة
$$3+\max(20,19)=23.$$
إذن أكبر مجموع للمسار هو \(23\). والمدخل الحقيقي ذو الصفوف الخمسة عشر يُحل بالطريقة نفسها تمامًا، ولكن عبر عدد أكبر من عمليات الدمج الصاعد.
تقوم تطبيقات C++ وPython وJava بتضمين المثلث ذي الصفوف الخمسة عشر مباشرة، ثم تنسخ الصف الأخير إلى مصفوفة عمل أحادية البعد. وعند هذه اللحظة تكون هذه المصفوفة مساوية بالفعل للقيم الصحيحة \(F(h-1,c)\) على القاعدة.
بعد ذلك تتحرك التطبيقات من الصف قبل الأخير حتى القمة. وفي كل موضع تستبدل قيمة العمل الحالية بــ "قيمة الخلية الحالية زائد الأكبر بين ابنيها". لا حاجة إلى تخزين الجدول كله، لأن الصف \(r\) يعتمد فقط على الصف \(r+1\).
وترتيب التحديث داخل المكان آمن؛ فعند تحديث موضع ما تكون القيمتان اللتان تمثلان الابنين ما تزالان تعبّران عن الصف الأسفل. وبعد الانتهاء من الصف \(r\)، تصبح أول \(r+1\) قيم في مصفوفة العمل مساوية تمامًا لـ \(F(r,0),F(r,1),\dots,F(r,r)\). كما تتحقق التطبيقات الثلاثة أيضًا من أن جواب المثال ذي الصفوف الأربعة هو \(23\).
المثلث ذو الارتفاع \(h\) يحتوي على
$$N=\frac{h(h+1)}{2}$$
قيمة. وتقوم البرمجة الديناميكية بمعالجة كل خلية غير موجودة في القاعدة مرة واحدة، ولذلك يكون الزمن \(O(N)\)، أو بصورة مكافئة \(O(h^2)\). أما الذاكرة الإضافية فهي \(O(h)\)، لأننا نحتفظ بصف عمل واحد فقط.
في Problem 18 تحديدًا، لدينا \(h=15\) و\(N=120\). وبعد نسخ صف القاعدة، تنفذ مرحلة الاختزال الصاعد \(1+2+\cdots+14=105\) تحديثات فقط، وهو أقل بكثير من فحص جميع المسارات الكاملة وعددها \(2^{14}=16384\).