The Triangle

Problem Statement Given a triangle of n rows of positive integers, find a path from the top to the bottom such that the sum of the numbers along the path is maximized. At each step, you may move to the element directl...

Updated May 21, 2026

Track IOI

Year 1994

Statement Rendered from TeX

TeXC++Rendered statement

Problem statement

Problem Statement

Rendered from the "Problem Statement" section in the LaTeX write-up.

Open TeX section

Given a triangle of $n$ rows of positive integers, find a path from the top to the bottom such that the sum of the numbers along the path is maximized. At each step, you may move to the element directly below or to the element directly below and one position to the right.

Example:

The maximum sum path is $7 \to 3 \to 8 \to 7 \to 5 = 30$.

Constraints: $1 \le n \le 100$, each element is between 0 and 99.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Solution Approach

This is a classic dynamic programming problem. We define: \[ \text{dp}[i][j] = \text{maximum sum achievable from element } (i,j) \text{ down to the bottom row} \]

Base Case

For the bottom row $i = n-1$: \[ \text{dp}[n-1][j] = \text{val}[n-1][j] \]

Recurrence

For rows $i = n-2$ down to $0$: \[ \text{dp}[i][j] = \text{val}[i][j] + \max\!\big(\text{dp}[i+1][j],\;\text{dp}[i+1][j+1]\big) \]

Answer

The answer is $\text{dp}[0][0]$.

Why Bottom-Up?

Bottom-up DP avoids recursion overhead and is straightforward: we start from the last row and propagate maxima upward. The triangle can be modified in place, requiring no extra memory beyond the input array.

C++ Solution

#include <cstdio>
#include <algorithm>
using namespace std;

int tri[101][101];

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            scanf("%d", &tri[i][j]);

    // Bottom-up DP: modify triangle in place
    for (int i = n - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            tri[i][j] += max(tri[i + 1][j], tri[i + 1][j + 1]);

    printf("%d\n", tri[0][0]);
    return 0;
}

Complexity Analysis

Time complexity: $O(n^2)$. We visit each element of the triangle exactly once. The total number of elements is $\frac{n(n+1)}{2}$, so the work is $\Theta(n^2)$.
Space complexity: $O(n^2)$ for storing the triangle. Since we modify the triangle in place, no additional space is needed beyond the input. Alternatively, one could use a 1D array of size $n$ for a rolling approach, yielding $O(n)$ extra space.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 1994 - The Triangle
// Bottom-up DP: find max-sum path from top to bottom
// Time: O(n^2), Space: O(n^2)
#include <bits/stdc++.h>
using namespace std;

int tri[101][101];

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            scanf("%d", &tri[i][j]);

    // Bottom-up DP: modify triangle in place
    for (int i = n - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            tri[i][j] += max(tri[i + 1][j], tri[i + 1][j + 1]);

    printf("%d\n", tri[0][0]);
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/1994/triangle/solution.texC++ implementationcompetitive_programming/ioi/1994/triangle/solution.cpp