The input is a triangle of integers with 100 rows. If the entry in row \(i\) and column \(j\) is denoted by \(a_{i,j}\) with \(0 \le j \le i < 100\), a valid path starts at \(a_{0,0}\) and, at each step, moves either to \(a_{i+1,j}\) or to \(a_{i+1,j+1}\). The task is to maximize the sum of all visited entries. Since there are 99 downward choices, a brute-force search would have to inspect \(2^{99}\) different paths, so the problem must be reduced mathematically rather than solved by enumeration.
The central idea is that once a path reaches a given cell, the best continuation below that cell no longer depends on the earlier part of the path. That makes the triangle a natural dynamic-programming object.
Define \(F(i,j)\) to be the maximum total obtainable from cell \((i,j)\) down to the base of the triangle, including \(a_{i,j}\) itself. With this notation, the required answer is simply \(F(0,0)\).
On the last row there is no choice left, so the boundary condition is immediate:
$$F(n-1,j)=a_{n-1,j}, \qquad 0 \le j < n,$$
where \(n=100\).
From \((i,j)\) there are exactly two admissible children: \((i+1,j)\) and \((i+1,j+1)\). Any optimal path from \((i,j)\) must pick one of those children first and then continue optimally from the chosen child. Therefore
$$F(i,j)=a_{i,j}+\max\bigl(F(i+1,j),\,F(i+1,j+1)\bigr), \qquad 0 \le i < n-1,\; 0 \le j \le i.$$
This recurrence compresses the entire subtriangle below \((i,j)\) into one number: the best path sum available from that point onward.
If the rows are processed in the order \(n-2,n-3,\dots,0\), then when row \(i\) is updated, both children of every cell in that row already store their correct \(F\)-values. Replacing each entry by its value plus the larger child therefore produces the correct \(F(i,j)\) for every position in row \(i\).
This gives a clean invariant: after finishing row \(i\), every entry in that row equals the best possible total from that cell to the bottom. By induction on the row index, the invariant propagates all the way to row 0, and the single entry at the top becomes the global optimum.
The same invariant also explains why the computation can be done in place. Once row \(i+1\) has been used to update row \(i\), the original values in row \(i+1\) are never needed again, so the triangle itself can serve as the dynamic-programming table.
Consider the sample triangle with rows \(3\), \(7,4\), \(2,4,6\), and \(8,5,9,3\). The last row is already final. Moving one row upward gives
$$\bigl(2+\max(8,5),\;4+\max(5,9),\;6+\max(9,3)\bigr)=(10,13,15).$$
The next row becomes
$$\bigl(7+\max(10,13),\;4+\max(13,15)\bigr)=(20,19),$$
and the top entry becomes
$$3+\max(20,19)=23.$$
So the optimal path sum is 23, realized by the path \(3 \to 7 \to 4 \to 9\).
A path-by-path search grows exponentially because every step branches into two possible continuations. The recurrence avoids that explosion by solving each subtriangle once. For a 100-row triangle there are only \(100 \cdot 101 / 2 = 5050\) cells, so the entire problem collapses to a short pass over those entries instead of an astronomical search through \(2^{99}\) full paths.
The C++, Python, and Java implementations read the input as text, split it into lines, ignore blank lines, and parse each row into integers. The resulting nested container has row lengths \(1,2,3,\dots,100\), matching the geometry assumed by the recurrence.
They then iterate from the second-last row toward the top. For each entry, the implementation adds the larger of the two children directly below it. After one complete pass over a row, that row no longer stores raw triangle values; it stores the best suffix sums defined by \(F(i,j)\). When the loop reaches the top, the single remaining value is the maximum path sum for the whole triangle.
Each implementation includes a built-in checkpoint using the standard four-row sample. That check confirms that the bottom-up update produces 23 before the full 100-row triangle is processed. Aside from lightweight argument handling for the input source, the program is essentially the recurrence written directly into code.
If the triangle has \(n\) rows, then it contains \(N=n(n+1)/2\) entries. The algorithm performs one update for every entry outside the last row, so the running time is \(\Theta(N)=\Theta(n^2)\). For Problem 67, \(N=5050\), which is tiny compared with \(2^{99}\).
The extra memory usage is \(O(1)\) beyond the mutable triangle, because the dynamic-programming values are written back into the same structure. If the input had to remain unchanged, the same recurrence could still be evaluated with an \(O(n)\) buffer containing one row of suffix sums.
Gegeben ist ein Zahlendreieck mit 100 Zeilen. Bezeichne den Eintrag in Zeile \(i\) und Spalte \(j\) mit \(a_{i,j}\), wobei \(0 \le j \le i < 100\) gilt. Ein zulässiger Pfad beginnt bei \(a_{0,0}\) und geht in jedem Schritt entweder zu \(a_{i+1,j}\) oder zu \(a_{i+1,j+1}\). Gesucht ist die größtmögliche Summe aller besuchten Einträge. Da es 99 Entscheidungen nach unten gibt, müsste eine naive Suche \(2^{99}\) verschiedene Pfade prüfen; die Lösung muss also die Struktur des Problems ausnutzen.
Der entscheidende Punkt ist, dass die beste Fortsetzung unterhalb einer Zelle nur von dieser Zelle abhängt und nicht davon, wie man sie erreicht hat. Genau das ist die typische Situation für dynamische Programmierung.
Definiere \(F(i,j)\) als die maximal erreichbare Summe von der Zelle \((i,j)\) bis zur Basis des Dreiecks, einschließlich \(a_{i,j}\). Dann ist die gesuchte Antwort einfach \(F(0,0)\).
In der letzten Zeile gibt es keine weitere Wahl mehr. Deshalb lautet die Randbedingung
$$F(n-1,j)=a_{n-1,j}, \qquad 0 \le j < n,$$
wobei \(n=100\) ist.
Von \((i,j)\) aus sind nur zwei Kinder erreichbar: \((i+1,j)\) und \((i+1,j+1)\). Jeder optimale Pfad von \((i,j)\) muss zuerst eines dieser Kinder wählen und sich danach von dort optimal fortsetzen. Daher gilt
$$F(i,j)=a_{i,j}+\max\bigl(F(i+1,j),\,F(i+1,j+1)\bigr), \qquad 0 \le i < n-1,\; 0 \le j \le i.$$
Diese Formel fasst das gesamte untere Teil-Dreieck in einer einzigen Zahl zusammen: der besten noch erreichbaren Summe ab der aktuellen Position.
Verarbeitet man die Zeilen in der Reihenfolge \(n-2,n-3,\dots,0\), dann stehen beim Aktualisieren der Zeile \(i\) in beiden Kindern jeder Zelle bereits die korrekten \(F\)-Werte. Ersetzt man also den Eintrag durch seinen Wert plus das größere Kind, erhält man genau \(F(i,j)\).
Daraus folgt eine saubere Invariante: Nach Abschluss der Zeile \(i\) enthält jede Position dieser Zeile die beste erreichbare Summe von dort bis zum Ende. Eine Induktion über die Zeilennummer zeigt, dass diese Aussage bis ganz nach oben gültig bleibt; am Ende steht im obersten Eintrag das globale Optimum.
Dies erklärt zugleich die In-place-Berechnung. Sobald Zeile \(i+1\) zur Aktualisierung von Zeile \(i\) verwendet wurde, werden die ursprünglichen Werte von Zeile \(i+1\) nicht mehr benötigt. Das Dreieck selbst kann daher als DP-Tabelle dienen.
Betrachte das Beispieldreieck mit den Zeilen \(3\), \(7,4\), \(2,4,6\) und \(8,5,9,3\). Die letzte Zeile ist bereits fertig. Eine Zeile darüber erhält man
$$\bigl(2+\max(8,5),\;4+\max(5,9),\;6+\max(9,3)\bigr)=(10,13,15).$$
Die nächste Zeile wird zu
$$\bigl(7+\max(10,13),\;4+\max(13,15)\bigr)=(20,19),$$
und ganz oben steht schließlich
$$3+\max(20,19)=23.$$
Die maximale Pfadsumme ist also 23, erreicht durch den Pfad \(3 \to 7 \to 4 \to 9\).
Eine vollständige Pfadsuche wächst exponentiell, weil jeder Schritt zwei Fortsetzungen eröffnet. Die Rekurrenz vermeidet diese Explosion, indem jedes Teil-Dreieck genau einmal ausgewertet wird. Bei 100 Zeilen gibt es nur \(100 \cdot 101 / 2 = 5050\) Zellen, also wird das Problem auf einen kurzen Durchlauf über diese Einträge reduziert, statt \(2^{99}\) ganze Pfade zu verfolgen.
Die C++-, Python- und Java-Implementierungen lesen den Eingang als Text, zerlegen ihn in Zeilen, überspringen leere Zeilen und wandeln jede Zeile in Ganzzahlen um. Dadurch entsteht eine verschachtelte, veränderbare Struktur mit Zeilenlängen \(1,2,3,\dots,100\), genau passend zur geometrischen Form des Dreiecks.
Anschließend laufen die Implementierungen von der vorletzten Zeile bis nach oben. Für jeden Eintrag wird das größere der beiden Kinder addiert. Nach einem vollständigen Durchgang enthält die bearbeitete Zeile keine Rohdaten mehr, sondern die besten Suffixsummen \(F(i,j)\). Wenn die Schleife die Spitze erreicht, ist der verbleibende Einzelwert die maximale Pfadsumme des ganzen Dreiecks.
Jede Implementierung enthält außerdem einen Test mit dem bekannten Vier-Zeilen-Beispiel. Damit wird vor der eigentlichen Rechnung geprüft, dass die Bottom-up-Aktualisierung tatsächlich den Wert 23 liefert. Abgesehen von etwas Argumentbehandlung für die Eingabequelle ist das Programm im Kern genau die oben hergeleitete Rekurrenz.
Hat das Dreieck \(n\) Zeilen, dann besitzt es \(N=n(n+1)/2\) Einträge. Der Algorithmus führt für jeden Eintrag außerhalb der letzten Zeile genau ein Update aus, also beträgt die Laufzeit \(\Theta(N)=\Theta(n^2)\). Für Problem 67 ist \(N=5050\), was gegenüber \(2^{99}\) verschwindend klein ist.
Der zusätzliche Speicherbedarf ist \(O(1)\) über dem veränderbaren Dreieck, weil die DP-Werte direkt in dieselbe Struktur zurückgeschrieben werden. Falls die Eingabe unverändert bleiben müsste, könnte dieselbe Rekurrenz immer noch mit einem \(O(n)\)-Puffer für eine einzige Zeile ausgeführt werden.
Verilen nesne 100 satırlı bir sayı üçgenidir. \(i\). satırın \(j\). sütunundaki değeri \(a_{i,j}\) ile gösterelim; burada \(0 \le j \le i < 100\) koşulu vardır. Geçerli bir yol \(a_{0,0}\) noktasından başlar ve her adımda ya \(a_{i+1,j}\) hücresine ya da \(a_{i+1,j+1}\) hücresine iner. Amaç, ziyaret edilen sayıların toplamını en büyük yapmaktır. Aşağı doğru 99 karar bulunduğu için kaba kuvvet yaklaşımı \(2^{99}\) farklı yolu denemek zorunda kalır; bu yüzden çözüm, tüm yolları tek tek saymak yerine yapıyı özetlemelidir.
Temel gözlem şudur: Bir yol belirli bir hücreye ulaştıktan sonra, o hücrenin altındaki en iyi devam yolu artık geçmişte hangi seçimlerin yapıldığına bağlı değildir. Bu da problemi dinamik programlama için doğal hâle getirir.
\(F(i,j)\) değerini, \((i,j)\) hücresinden üçgenin tabanına kadar elde edilebilecek en büyük toplam olarak tanımlayalım; \(a_{i,j}\) de bu toplama dahildir. O hâlde aradığımız cevap doğrudan \(F(0,0)\) olur.
Son satırda artık seçim kalmadığı için sınır koşulu hemen yazılır:
$$F(n-1,j)=a_{n-1,j}, \qquad 0 \le j < n,$$
burada \(n=100\) kabul edilir.
\((i,j)\) hücresinden sadece iki çocuk erişilebilir: \((i+1,j)\) ve \((i+1,j+1)\). \((i,j)\) noktasından başlayan en iyi yol önce bu iki çocuktan birini seçmek zorundadır; seçilen çocuktan sonrası da yine en iyi şekilde devam etmelidir. Bu nedenle
$$F(i,j)=a_{i,j}+\max\bigl(F(i+1,j),\,F(i+1,j+1)\bigr), \qquad 0 \le i < n-1,\; 0 \le j \le i.$$
Bu bağıntı, \((i,j)\) hücresinin altındaki bütün alt üçgeni tek bir sayı ile temsil eder: o noktadan aşağıya doğru elde edilebilecek en iyi toplam.
Satırlar \(n-2,n-3,\dots,0\) sırasıyla işlendiğinde, \(i\). satır güncellenirken her hücrenin iki çocuğu zaten doğru \(F\)-değerlerini taşır. Bu yüzden ilgili hücreye kendi değeri ile iki çocuğun büyüğü eklendiğinde, ortaya tam olarak \(F(i,j)\) çıkar.
Böylece açık bir değişmez elde edilir: \(i\). satır bittiğinde, o satırdaki her giriş kendi konumundan tabana kadar olan en iyi toplamı saklar. Satır numarası üzerinde yapılacak basit bir tümevarım, bu özelliğin en alta yakın satırlardan tepeye kadar taşındığını gösterir. Sonuçta üstte kalan tek sayı küresel optimumdur.
Aynı değişmez, neden işlemin yerinde yapılabildiğini de açıklar. \(i+1\). satır, \(i\). satırı güncellemek için kullanıldıktan sonra artık eski hâliyle gerekli değildir. Dolayısıyla üçgenin kendisi dinamik programlama tablosu olarak kullanılabilir.
Örnek olarak satırları \(3\), \(7,4\), \(2,4,6\) ve \(8,5,9,3\) olan küçük üçgeni ele alalım. Son satır zaten hazırdır. Bir üst satır şu şekilde güncellenir:
$$\bigl(2+\max(8,5),\;4+\max(5,9),\;6+\max(9,3)\bigr)=(10,13,15).$$
Onun üstündeki satır
$$\bigl(7+\max(10,13),\;4+\max(13,15)\bigr)=(20,19)$$
olur ve tepedeki sayı da
$$3+\max(20,19)=23$$
şeklinde bulunur. Böylece en iyi yol toplamı 23 olur; bunu veren yol \(3 \to 7 \to 4 \to 9\) yoludur.
Her adımda iki seçenek oluştuğu için tam yol araması üstel büyür. Özyineleme ise her alt üçgeni yalnızca bir kez çözer. 100 satırlı bu problemde toplam hücre sayısı sadece \(100 \cdot 101 / 2 = 5050\) olduğundan, astronomik büyüklükteki \(2^{99}\) yol yerine birkaç bin hücre üzerinde tek bir geçiş yeterlidir.
C++, Python ve Java uygulamaları girdiyi metin olarak okur, satırlara ayırır, boş satırları atlar ve her satırı tam sayılara dönüştürür. Elde edilen iç içe yapı, uzunlukları \(1,2,3,\dots,100\) olan satırlardan oluşur; bu da özyinelemenin kullandığı üçgensel geometri ile birebir uyumludur.
Daha sonra döngü, sondan bir önceki satırdan başlayıp tepeye kadar ilerler. Her hücre için altındaki iki çocuğun büyüğü o hücreye eklenir. Bir satır tamamen işlendiğinde, artık ham giriş değerlerini değil, \(F(i,j)\) ile tanımlanan en iyi kuyruk toplamlarını taşır. Döngü tepeye ulaştığında kalan tek değer bütün üçgenin maksimum yol toplamıdır.
Her uygulamada standart dört satırlı örnek üzerinde bir denetim de vardır. Bu denetim, tam girdi işlenmeden önce aşağıdan yukarıya güncellemenin gerçekten 23 ürettiğini doğrular. Girdi kaynağı için yapılan hafif argüman işleme dışında programın özü, yukarıdaki bağıntının doğrudan uygulanmasından ibarettir.
Üçgenin \(n\) satırı varsa toplam giriş sayısı \(N=n(n+1)/2\) olur. Algoritma son satır dışındaki her giriş için tam bir güncelleme yaptığı için çalışma süresi \(\Theta(N)=\Theta(n^2)\) olur. Problem 67 için \(N=5050\) olduğundan bu maliyet, \(2^{99}\) ile karşılaştırıldığında çok küçüktür.
Ek bellek kullanımı, değiştirilebilir üçgenin ötesinde \(O(1)\) düzeyindedir; çünkü dinamik programlama değerleri aynı yapının içine geri yazılır. Eğer girişin korunması zorunlu olsaydı, aynı bağıntı tek bir satırlık \(O(n)\) tamponla da yürütülebilirdi.
La entrada es un triángulo de enteros con 100 filas. Si denotamos por \(a_{i,j}\) el valor de la fila \(i\) y la columna \(j\), con \(0 \le j \le i < 100\), un camino válido empieza en \(a_{0,0}\) y en cada paso baja a \(a_{i+1,j}\) o a \(a_{i+1,j+1}\). El objetivo es maximizar la suma de los valores visitados. Como hay 99 decisiones hacia abajo, una búsqueda por fuerza bruta tendría que examinar \(2^{99}\) caminos distintos, así que la clave está en resumir subproblemas en lugar de enumerar rutas completas.
La observación decisiva es que, una vez que un camino ha llegado a una celda, la mejor continuación por debajo de esa celda ya no depende de cómo se llegó hasta allí. Esa independencia es exactamente lo que hace viable la programación dinámica.
Definimos \(F(i,j)\) como la suma máxima que puede obtenerse desde la celda \((i,j)\) hasta la base del triángulo, incluyendo \(a_{i,j}\). Con esta definición, la respuesta buscada es \(F(0,0)\).
En la última fila no queda ninguna elección, de modo que la condición de borde es
$$F(n-1,j)=a_{n-1,j}, \qquad 0 \le j < n,$$
donde \(n=100\).
Desde \((i,j)\) solo se puede pasar a dos hijos: \((i+1,j)\) y \((i+1,j+1)\). Cualquier camino óptimo desde \((i,j)\) debe escoger primero uno de esos dos hijos y, después, continuar óptimamente desde el hijo elegido. Por tanto,
$$F(i,j)=a_{i,j}+\max\bigl(F(i+1,j),\,F(i+1,j+1)\bigr), \qquad 0 \le i < n-1,\; 0 \le j \le i.$$
La recurrencia resume todo el subtriángulo inferior en un solo número: la mejor suma posible a partir de la celda actual.
Si procesamos las filas en el orden \(n-2,n-3,\dots,0\), entonces al actualizar la fila \(i\) los dos hijos de cada celda ya contienen sus valores correctos de \(F\). Reemplazar la celda por su valor más el mayor de los dos hijos produce exactamente \(F(i,j)\).
De ahí sale un invariante claro: al terminar la fila \(i\), cada entrada de esa fila almacena la mejor suma posible desde esa posición hasta la base. Una inducción sobre el índice de fila demuestra que el invariante sube intacto hasta la cima; al final, el único valor de la fila superior es el óptimo global.
El mismo razonamiento explica por qué puede hacerse todo en el propio triángulo. Una vez que la fila \(i+1\) ya sirvió para actualizar la fila \(i\), sus valores originales no vuelven a ser necesarios, así que la estructura de entrada actúa al mismo tiempo como tabla de programación dinámica.
Tomemos el triángulo de ejemplo con filas \(3\), \(7,4\), \(2,4,6\) y \(8,5,9,3\). La última fila ya es definitiva. La fila inmediatamente superior se convierte en
$$\bigl(2+\max(8,5),\;4+\max(5,9),\;6+\max(9,3)\bigr)=(10,13,15).$$
La siguiente fila pasa a ser
$$\bigl(7+\max(10,13),\;4+\max(13,15)\bigr)=(20,19),$$
y la cima queda
$$3+\max(20,19)=23.$$
Por lo tanto, la suma máxima es 23, conseguida por el camino \(3 \to 7 \to 4 \to 9\).
Un recorrido explícito de caminos crece exponencialmente porque cada paso abre dos continuaciones. La recurrencia evita esa explosión resolviendo cada subtriángulo una sola vez. En este problema hay únicamente \(100 \cdot 101 / 2 = 5050\) celdas, así que el cálculo real es un único barrido corto sobre esos números y no una exploración de \(2^{99}\) rutas completas.
Las implementaciones en C++, Python y Java leen la entrada como texto, la dividen en líneas, ignoran las líneas vacías y convierten cada fila en enteros. El resultado es un contenedor anidado y mutable cuyas longitudes de fila son \(1,2,3,\dots,100\), exactamente la forma que requiere la recurrencia.
Después recorren el triángulo desde la penúltima fila hasta la primera. En cada posición, el valor almacenado se reemplaza por él mismo más el mayor de sus dos hijos. Cuando una fila termina de procesarse, ya no guarda datos originales, sino los mejores valores \(F(i,j)\). Cuando el bucle alcanza la parte superior, el número restante es la suma máxima del triángulo entero.
Cada implementación incluye una verificación con el ejemplo clásico de cuatro filas. Esa comprobación asegura que la actualización ascendente produce 23 antes de atacar la entrada completa. Fuera de un manejo ligero de argumentos para la fuente de entrada, el programa no hace más que ejecutar la recurrencia derivada arriba.
Si el triángulo tiene \(n\) filas, contiene \(N=n(n+1)/2\) entradas. El algoritmo realiza una actualización por cada entrada fuera de la última fila, así que el tiempo es \(\Theta(N)=\Theta(n^2)\). Para el Problema 67, \(N=5050\), una cantidad minúscula frente a \(2^{99}\).
El uso de memoria adicional es \(O(1)\) aparte del propio triángulo mutable, porque los valores de programación dinámica se escriben en la misma estructura. Si hubiera que conservar la entrada intacta, la misma idea seguiría funcionando con un búfer de \(O(n)\) que almacenara una sola fila de sumas óptimas.
题目给出一个包含 100 行整数的数字三角形。把第 \(i\) 行第 \(j\) 个数记为 \(a_{i,j}\)，其中 \(0 \le j \le i < 100\)。一条合法路径从 \(a_{0,0}\) 出发，每下一层只能走到 \(a_{i+1,j}\) 或 \(a_{i+1,j+1}\)。目标是让经过数字的总和尽可能大。由于一共要做 99 次向下选择，直接暴力枚举需要检查 \(2^{99}\) 条路径，因此必须把问题压缩成可复用的子问题。
真正关键的观察是：一条路径一旦到达某个位置，该位置以下的最优延续只取决于当前位置本身，而与此前如何到达这里无关。这正是动态规划最适合处理的结构。
定义 \(F(i,j)\) 为从单元 \((i,j)\) 走到底边时能够得到的最大总和，并且这个总和包含当前位置 \(a_{i,j}\)。这样一来，题目的答案就是 \(F(0,0)\)。
最后一行已经没有后续选择，所以边界条件立刻得到：
$$F(n-1,j)=a_{n-1,j}, \qquad 0 \le j < n,$$
这里 \(n=100\)。
从 \((i,j)\) 只能走向两个子位置：\((i+1,j)\) 和 \((i+1,j+1)\)。因此，从 \((i,j)\) 出发的最优路径，第一步必然在这两个孩子中选一个；而选定之后，后面的部分也必须是从那个孩子出发的最优路径。于是有
$$F(i,j)=a_{i,j}+\max\bigl(F(i+1,j),\,F(i+1,j+1)\bigr), \qquad 0 \le i < n-1,\; 0 \le j \le i.$$
这个递推式把 \((i,j)\) 下方整个子三角形的信息压缩成一个值，也就是“从这里往下最好能拿到多少分”。
如果按 \(n-2,n-3,\dots,0\) 的顺序处理各行，那么在更新第 \(i\) 行时，该行每个位置的两个孩子都已经被替换成了正确的 \(F\)-值。于是，把当前值改成“自己加上两个孩子中的较大者”，就恰好得到该位置真正的 \(F(i,j)\)。
这给出一个非常清晰的不变式：当第 \(i\) 行处理完成后，这一行中的每个数都等于从该位置到底边的最优总和。对行号做简单归纳，就能说明这个不变式会一路向上传递到第 0 行。最后顶端只剩下一个数，它就是整个三角形的全局最优值。
同样的不变式还解释了为什么算法可以原地完成。第 \(i+1\) 行一旦被用来更新第 \(i\) 行，它的原始值就再也不会被访问，所以输入三角形本身就可以直接充当动态规划表。
看一下标准示例三角形，它的四行分别是 \(3\)、\(7,4\)、\(2,4,6\) 和 \(8,5,9,3\)。最后一行已经是最终值。向上更新一行得到
$$\bigl(2+\max(8,5),\;4+\max(5,9),\;6+\max(9,3)\bigr)=(10,13,15).$$
再往上一行得到
$$\bigl(7+\max(10,13),\;4+\max(13,15)\bigr)=(20,19),$$
最后顶部变成
$$3+\max(20,19)=23.$$
因此最大路径和是 23，对应路径是 \(3 \to 7 \to 4 \to 9\)。这个例子和 100 行的正式数据在数学上完全同构，只是规模更小。
如果把问题看成“试遍所有路径”，那么每下一层都分成两个分支，规模会指数爆炸。递推式的作用是让每个子三角形只求解一次。对于 100 行三角形，总共只有 \(100 \cdot 101 / 2 = 5050\) 个位置，因此真正需要做的只是对这些位置做一次短小的自底向上扫描，而不是在 \(2^{99}\) 条完整路径之间来回比较。
C++、Python 和 Java 三个实现都会先把输入按文本读取，再按行拆分，跳过空行，并把每一行解析成整数列表。最终得到的是一个可修改的嵌套结构，第 \(i\) 行恰好有 \(i+1\) 个元素，这与递推式默认的三角形布局完全一致。
随后，程序从倒数第二行开始向上遍历。对每个位置，都把“下面两个孩子中的较大者”加到当前位置上。某一行处理结束后，这一行保存的就不再是原始输入，而是对应的最优后缀和 \(F(i,j)\)。当循环走到最上面时，剩下的那个顶点值就是整个题目的最大路径和。
三个实现都包含对四行示例的检查，用来确认自底向上的更新确实会产生 23。除去少量与输入来源有关的参数处理之外，求解器的核心几乎就是把上面的递推式逐字落实为代码。
若三角形有 \(n\) 行，则总元素个数为 \(N=n(n+1)/2\)。算法对最后一行之外的每个位置做一次更新，所以总时间复杂度是 \(\Theta(N)=\Theta(n^2)\)。对本题而言，\(N=5050\)，与 \(2^{99}\) 相比几乎可以忽略不计。
额外空间复杂度在可修改三角形之外是 \(O(1)\)，因为动态规划值直接写回原结构。如果必须保留原输入不变，同样的递推仍然可以用一个 \(O(n)\) 的单行缓冲区完成。
Во входных данных дан числовой треугольник из 100 строк. Обозначим элемент в строке \(i\) и столбце \(j\) через \(a_{i,j}\), где \(0 \le j \le i < 100\). Допустимый путь начинается в \(a_{0,0}\) и на каждом шаге переходит либо в \(a_{i+1,j}\), либо в \(a_{i+1,j+1}\). Нужно максимизировать сумму всех посещенных чисел. Поскольку вниз совершается 99 выборов, полный перебор потребовал бы рассмотреть \(2^{99}\) путей, а значит, решение должно опираться на структуру задачи, а не на перечисление всех вариантов.
Главное наблюдение состоит в том, что после попадания в фиксированную клетку лучший путь ниже нее уже не зависит от того, каким маршрутом мы пришли в эту клетку. Именно такая независимость и делает динамическое программирование естественным инструментом.
Обозначим через \(F(i,j)\) максимальную сумму, которую можно получить, начиная из клетки \((i,j)\) и заканчивая на основании треугольника, включая само значение \(a_{i,j}\). Тогда искомый ответ равен \(F(0,0)\).
На последней строке выбора уже нет, поэтому граничное условие выглядит так:
$$F(n-1,j)=a_{n-1,j}, \qquad 0 \le j < n,$$
где \(n=100\).
Из клетки \((i,j)\) можно перейти только к двум потомкам: \((i+1,j)\) и \((i+1,j+1)\). Следовательно, любой оптимальный путь из \((i,j)\) обязан сначала выбрать одного из этих двух потомков, а затем продолжиться оптимально уже из выбранной клетки. Поэтому
$$F(i,j)=a_{i,j}+\max\bigl(F(i+1,j),\,F(i+1,j+1)\bigr), \qquad 0 \le i < n-1,\; 0 \le j \le i.$$
Эта формула сворачивает весь под-треугольник под \((i,j)\) в одно число: в лучшую сумму, достижимую из данной позиции вниз.
Если обрабатывать строки в порядке \(n-2,n-3,\dots,0\), то к моменту обновления строки \(i\) оба потомка каждой ее клетки уже содержат правильные значения \(F\). Значит, если заменить элемент на его собственное значение плюс максимум из двух потомков, получится ровно \(F(i,j)\).
Отсюда возникает удобный инвариант: после завершения строки \(i\) каждый элемент этой строки хранит наилучшую возможную сумму от своей клетки до основания. Простая индукция по номеру строки показывает, что инвариант поднимается до самой вершины. В результате единственное число наверху и есть глобальный оптимум.
Тот же инвариант объясняет и вычисление на месте. После того как строка \(i+1\) использована для обновления строки \(i\), исходные значения строки \(i+1\) больше не нужны. Поэтому сам треугольник можно использовать как таблицу динамического программирования.
Возьмем стандартный пример с рядами \(3\), \(7,4\), \(2,4,6\) и \(8,5,9,3\). Последняя строка уже окончательная. Строка над ней превращается в
$$\bigl(2+\max(8,5),\;4+\max(5,9),\;6+\max(9,3)\bigr)=(10,13,15).$$
Следующая строка становится
$$\bigl(7+\max(10,13),\;4+\max(13,15)\bigr)=(20,19),$$
а вершина равна
$$3+\max(20,19)=23.$$
Значит, максимальная сумма пути равна 23 и достигается по маршруту \(3 \to 7 \to 4 \to 9\).
Явный перебор путей растет экспоненциально, потому что на каждом шаге возникают две развилки. Рекуррентная формула устраняет этот взрыв, поскольку каждый под-треугольник решается только один раз. В задаче со 100 строками имеется всего \(100 \cdot 101 / 2 = 5050\) клеток, так что вместо астрономического числа \(2^{99}\) путей нужно один раз пройтись по нескольким тысячам элементов.
Реализации на C++, Python и Java читают вход как текст, разбивают его на строки, пропускают пустые строки и преобразуют каждую строку в список целых чисел. В результате получается изменяемая вложенная структура, где длины строк равны \(1,2,3,\dots,100\), то есть точно соответствуют форме треугольника.
Затем программа идет от предпоследней строки вверх. Для каждой позиции она добавляет к текущему значению максимум из двух потомков. После обработки строки в ней хранятся уже не исходные данные, а значения \(F(i,j)\), то есть лучшие суммы от соответствующих клеток до основания. Когда цикл доходит до вершины, оставшееся число и есть ответ для всего треугольника.
Во всех трех версиях есть контрольный пример из четырех строк. Он проверяет, что проход снизу вверх действительно выдает 23 еще до обработки полного входа. За исключением небольшого разбора аргументов, связанного с источником данных, программа представляет собой почти прямую запись выведенной выше рекуррентной формулы.
Если у треугольника \(n\) строк, то общее число элементов равно \(N=n(n+1)/2\). Алгоритм выполняет одно обновление для каждого элемента вне последней строки, поэтому время работы равно \(\Theta(N)=\Theta(n^2)\). Для задачи 67 это \(N=5050\), что ничтожно мало по сравнению с \(2^{99}\).
Дополнительная память сверх изменяемого треугольника составляет \(O(1)\), потому что значения динамического программирования записываются обратно в ту же структуру. Если бы вход нужно было сохранить неизменным, ту же идею можно было бы реализовать с буфером размера \(O(n)\), хранящим одну строку оптимальных сумм.
المعطى هو مثلث من الأعداد الصحيحة مكوَّن من 100 صف. إذا رمزنا إلى العنصر في الصف \(i\) والعمود \(j\) بالرمز \(a_{i,j}\)، بحيث \(0 \le j \le i < 100\)، فإن المسار المسموح يبدأ من \(a_{0,0}\) وفي كل خطوة يهبط إمّا إلى \(a_{i+1,j}\) أو إلى \(a_{i+1,j+1}\). المطلوب هو تعظيم مجموع القيم التي يمر بها المسار. وبما أن هناك 99 قرارًا نزوليًا، فإن البحث بالقوة الغاشمة يحتاج إلى فحص \(2^{99}\) مسارًا مختلفًا، ولذلك لا بد من اختزال المسألة إلى مسائل فرعية قابلة لإعادة الاستخدام.
الفكرة الحاسمة هي أن المسار، بعد أن يصل إلى خلية معيّنة، لا يعود يهتم بكيفية الوصول إلى تلك الخلية؛ فالجزء الأفضل أسفلها يعتمد على موضعها الحالي فقط. وهذه بالضبط البنية التي تجعل البرمجة الديناميكية أداة طبيعية هنا.
لنعرّف \(F(i,j)\) على أنه أكبر مجموع يمكن الحصول عليه ابتداءً من الخلية \((i,j)\) نزولًا إلى قاعدة المثلث، مع احتساب القيمة \(a_{i,j}\) نفسها. عندئذٍ تصبح الإجابة المطلوبة ببساطة هي \(F(0,0)\).
في الصف الأخير لا يبقى أي اختيار، ولذلك تكون حالة الحد مباشرة:
$$F(n-1,j)=a_{n-1,j}, \qquad 0 \le j < n,$$
حيث \(n=100\).
من الخلية \((i,j)\) لا يمكن النزول إلا إلى ولدين اثنين: \((i+1,j)\) و\((i+1,j+1)\). لذلك فإن أي مسار أمثل يبدأ من \((i,j)\) لا بد أن يختار أحد هذين الولدين أولًا، ثم يتابع من الخلية المختارة بأفضل صورة ممكنة. ومن هنا نحصل على
$$F(i,j)=a_{i,j}+\max\bigl(F(i+1,j),\,F(i+1,j+1)\bigr), \qquad 0 \le i < n-1,\; 0 \le j \le i.$$
هذه العلاقة تختزل المثلث الفرعي كله الواقع أسفل \((i,j)\) إلى عدد واحد فقط: أفضل مجموع يمكن تحقيقه انطلاقًا من هذا الموضع.
إذا عالجنا الصفوف بالترتيب \(n-2,n-3,\dots,0\)، فعند تحديث الصف \(i\) يكون ابنا كل خلية في هذا الصف قد تحوّلا بالفعل إلى القيم الصحيحة لـ \(F\). وعليه، فإن استبدال كل عنصر بقيمته زائد أكبر ولديه يعطي بالضبط \(F(i,j)\).
ومن هنا يظهر ثابت مهم: بعد الانتهاء من الصف \(i\)، تكون كل خلية فيه قد أصبحت تساوي أفضل مجموع ممكن من ذلك الموضع حتى القاعدة. وباستقراء بسيط على رقم الصف، ينتقل هذا الثابت من الأسفل إلى الأعلى حتى نصل إلى القمة، حيث تصبح الخلية الوحيدة المتبقية هي الحل الأمثل للمسألة كلها.
وهذا الثابت نفسه يفسر أيضًا سبب إمكان إجراء الحساب في المكان نفسه. فبمجرد استخدام الصف \(i+1\) لتحديث الصف \(i\)، لا نعود بحاجة إلى قيمه الأصلية. لذلك يمكن أن يعمل المثلث نفسه بوصفه جدول البرمجة الديناميكية.
لنأخذ مثلث المثال القياسي ذي الصفوف \(3\)، ثم \(7,4\)، ثم \(2,4,6\)، ثم \(8,5,9,3\). الصف الأخير نهائي أصلًا. وعند الصعود صفًا واحدًا نحصل على
$$\bigl(2+\max(8,5),\;4+\max(5,9),\;6+\max(9,3)\bigr)=(10,13,15).$$
ثم يصبح الصف الذي فوقه
$$\bigl(7+\max(10,13),\;4+\max(13,15)\bigr)=(20,19),$$
وأخيرًا تصبح القمة
$$3+\max(20,19)=23.$$
إذًا فإن أكبر مجموع للمسار يساوي 23، ويتحقق على المسار \(3 \to 7 \to 4 \to 9\).
عند النظر إلى المسألة على أنها تعداد لجميع المسارات، فإن كل خطوة تضاعف عدد الاحتمالات تقريبًا، فيحدث نمو أسي سريع. أما العلاقة العودية فتجعل كل مثلث فرعي يُحل مرة واحدة فقط. ولأن عدد الخلايا في مثلث من 100 صف هو \(100 \cdot 101 / 2 = 5050\) فقط، فإن الحساب الحقيقي يتحول إلى مرور قصير على هذه الخلايا بدلًا من استكشاف \(2^{99}\) مسارًا كاملًا.
تقرأ تطبيقات C++ وPython وJava الدخل على هيئة نص، ثم تقسّمه إلى أسطر، وتتجاهل الأسطر الفارغة، وتحول كل صف إلى أعداد صحيحة. والنتيجة بنية متداخلة قابلة للتعديل، أطوال صفوفها هي \(1,2,3,\dots,100\)، وهي مطابقة تمامًا للشكل الهندسي الذي تفترضه العلاقة العودية.
بعد ذلك تبدأ الحلقة من الصف قبل الأخير وتصعد نحو الأعلى. في كل موضع، تضيف الشيفرة أكبر الابنين إلى القيمة الحالية. وبعد إنهاء صف كامل، لا يعود ذلك الصف يحتفظ بالقيم الخام، بل يحتفظ بقيم \(F(i,j)\) أي بأفضل المجاميع الممكنة من تلك الخلايا حتى القاعدة. وعندما تصل الحلقة إلى القمة، تكون القيمة الوحيدة الباقية هي مجموع المسار الأعظمي للمثلث كله.
تتضمن كل نسخة من التنفيذ اختبارًا داخليًا على المثال ذي الصفوف الأربعة. هذا الاختبار يتأكد من أن التحديث من الأسفل إلى الأعلى يعطي 23 قبل معالجة المثلث الكامل. وباستثناء قدر بسيط من التعامل مع وسائط مصدر الدخل، فإن جوهر البرنامج ليس أكثر من ترجمة مباشرة للعلاقة العودية السابقة.
إذا كان للمثلث \(n\) صفوف، فإن عدد عناصره هو \(N=n(n+1)/2\). وتنفذ الخوارزمية تحديثًا واحدًا لكل عنصر خارج الصف الأخير، لذلك يكون زمن التنفيذ \(\Theta(N)=\Theta(n^2)\). وفي هذه المسألة تحديدًا لدينا \(N=5050\)، وهو عدد ضئيل جدًا مقارنةً بـ \(2^{99}\).
أما الذاكرة الإضافية فهي \(O(1)\) فوق المثلث القابل للتعديل نفسه، لأن قيم البرمجة الديناميكية تُكتب داخل البنية ذاتها. ولو كان لا بد من الإبقاء على الدخل دون تغيير، فمن الممكن تنفيذ الفكرة نفسها باستخدام مخزن مؤقت حجمه \(O(n)\) يحتفظ بصف واحد من المجاميع المثلى.