Problem 907: Minimum Path Sum in Triangle

Mathematical Analysis

Optimal Substructure

A path from the apex $T(0,0)$ to the base row consists of $N$ entries, choosing at each row $i$ to step to position $j$ or $j+1$ in row $i+1$. The minimum path sum satisfies the Bellman equation:

with boundary $V(N-1, j) = T(N-1, j)$ for the bottom row.

Theorem (Optimal Substructure). Any prefix of an optimal path is itself optimal for the subproblem rooted at the corresponding node.

Proof. Suppose the optimal path from $(0,0)$ passes through $(i,j)$ with cost $C^*$. If there existed a better path from $(i,j)$ to the bottom with cost $C' < C^* - \text{cost}(0,0 \to i,j)$, then splicing it in would give a total cost less than $C^*$, contradicting optimality. $\square$

Bottom-Up Dynamic Programming

Working from row $N-1$ upward, equation (1) is evaluated in place:

1. Initialize $dp[j] = T(N-1, j)$ for $j = 0, \ldots, N-1$.
2. For $i = N-2$ down to $0$: for $j = 0, \ldots, i$: $dp[j] = T(i,j) + \min(dp[j], dp[j+1])$.
3. Answer: $dp[0]$.

Lemma (In-Place Correctness). Updating $dp[j]$ for $j = 0, 1, \ldots, i$ reads $dp[j]$ and $dp[j+1]$ from the previous (larger) row before overwriting, since $j$ is processed in increasing order and $dp[j+1]$ has not yet been updated.

Proof. At step $j$, $dp[j+1]$ still holds $V(i+1, j+1)$ because the loop processes $j$ from left to right, and $j+1 > j$ means $dp[j+1]$ has not been touched. $\square$

Properties of the Triangle Entries

The entries $T(i,j) = ((i+1)(j+1) \cdot 37 + 13) \bmod 100$ produce pseudo-random values in $[0, 99]$. The distribution is roughly uniform since $\gcd(37, 100) = 1$ (37 is coprime to 100), so the entries form a permutation-like pattern across residues.

Proposition. The expected value of a minimum path sum through an $N$-row triangle with i.i.d. uniform $[0, M-1]$ entries is approximately $N \cdot M / 3$.

Proof sketch. At each row, the path chooses the smaller of two adjacent entries. If entries are independent uniform on $[0, M-1]$, then $\mathbb{E}[\min(X, Y)] = (M-1)/3$. Over $N$ rows, the expected total is approximately $N(M-1)/3$. For $M = 100$, $N = 1000$: expected $\approx 33{,}000$. $\square$

Greedy vs. Optimal

A greedy strategy (always step to the smaller neighbor) does NOT guarantee optimality. The optimal path may choose a locally larger value to access a much smaller subtree.

Counterexample. Consider:

    1
   99  2
  1  99  99

Greedy from top: $1 \to 2 \to 99 = 102$. Optimal: $1 \to 99 \to 1 = 101$.

Verification Table

The per-row contribution of the min path decreases slowly as $N$ grows (approaching the $M/3 \approx 33$ limit).

Derivation

The algorithm is straightforward DP. The only subtlety is generating the triangle correctly (1-indexed vs 0-indexed) and the in-place update order.

Proof of Correctness

Theorem. The bottom-up DP correctly computes the minimum path sum.

Proof. By induction on row $i$ from $N-1$ to $0$. Base: $dp[j] = T(N-1,j) = V(N-1,j)$. Inductive step: if $dp[j] = V(i+1, j)$ for all $j$, then after updating row $i$: $dp[j] = T(i,j) + \min(V(i+1,j), V(i+1,j+1)) = V(i,j)$. The in-place update is safe as shown above. $\square$

Complexity Analysis

• Time: $O(N^2)$ — each entry is processed once. For $N = 1000$: about 500,000 operations.
• Space: $O(N)$ using a single row array (in-place DP).
• Brute-force (all paths): $O(2^N)$ — completely infeasible for $N = 1000$.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 907: Minimum Path Sum in Triangle
 *
 * Triangle: T(i,j) = ((i+1)*(j+1)*37 + 13) % 100, 0 <= j <= i, N = 1000 rows.
 * Find the minimum path sum from apex to base.
 *
 * Bellman equation: V(i,j) = T(i,j) + min(V(i+1,j), V(i+1,j+1))
 *
 * Method: Bottom-up DP in O(N^2) time, O(N) space.
 *
 * The in-place update processes j = 0..i left-to-right, which is safe
 * because dp[j+1] (from the previous row) is read before being overwritten.
 */

const int N = 1000;

int main() {
    // Generate triangle and perform bottom-up DP simultaneously
    // First, store the full triangle (needed for bottom-up)
    vector<vector<int>> tri(N);
    for (int i = 0; i < N; i++) {
        tri[i].resize(i + 1);
        for (int j = 0; j <= i; j++) {
            tri[i][j] = ((long long)(i + 1) * (j + 1) * 37 + 13) % 100;
        }
    }

    // Bottom-up DP
    vector<int> dp = tri[N - 1];
    for (int i = N - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[j] = tri[i][j] + min(dp[j], dp[j + 1]);
        }
    }

    cout << dp[0] << endl;

    // Verification for small N
    // Build small triangle and solve both by DP and brute-force (N=10)
    int sN = 10;
    vector<vector<int>> stri(sN);
    for (int i = 0; i < sN; i++) {
        stri[i].resize(i + 1);
        for (int j = 0; j <= i; j++)
            stri[i][j] = ((long long)(i + 1) * (j + 1) * 37 + 13) % 100;
    }

    // DP for small
    vector<int> sdp = stri[sN - 1];
    for (int i = sN - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            sdp[j] = stri[i][j] + min(sdp[j], sdp[j + 1]);

    // Brute-force DFS for small
    int best = INT_MAX;
    function<void(int, int, int)> dfs = [&](int i, int j, int total) {
        total += stri[i][j];
        if (i == sN - 1) {
            best = min(best, total);
            return;
        }
        dfs(i + 1, j, total);
        dfs(i + 1, j + 1, total);
    };
    dfs(0, 0, 0);

    assert(sdp[0] == best);

    return 0;
}

"""
Problem 907: Minimum Path Sum in Triangle

Given a triangle of N=1000 rows with T(i,j) = ((i+1)*(j+1)*37 + 13) % 100,
find the minimum path sum from apex to base.

Bellman equation: V(i,j) = T(i,j) + min(V(i+1,j), V(i+1,j+1))

Methods:
    1. Bottom-up DP (in-place): O(N^2) time, O(N) space
    2. Top-down with memoization: O(N^2) time, O(N^2) space
    3. Brute-force DFS (small N verification): O(2^N) time
"""

# Triangle generation
def make_triangle(N: int) -> list:
    """Generate the triangle: T(i,j) = ((i+1)*(j+1)*37 + 13) % 100."""
    return [[(( i + 1) * (j + 1) * 37 + 13) % 100 for j in range(i + 1)]
            for i in range(N)]

def min_path_dp(tri: list):
    """Compute minimum path sum using bottom-up DP.

    dp[j] starts as bottom row, then updated upward:
    dp[j] = tri[i][j] + min(dp[j], dp[j+1])
    """
    N = len(tri)
    dp = tri[-1][:]
    for i in range(N - 2, -1, -1):
        for j in range(i + 1):
            dp[j] = tri[i][j] + min(dp[j], dp[j + 1])
    return dp[0]

def min_path_topdown(tri: list):
    """Compute minimum path sum using top-down memoization."""
    import sys
    sys.setrecursionlimit(10000)
    N = len(tri)
    memo = {}

    def dp(i, j):
        if i == N - 1:
            return tri[i][j]
        if (i, j) not in memo:
            memo[(i, j)] = tri[i][j] + min(dp(i + 1, j), dp(i + 1, j + 1))
        return memo[(i, j)]

    return dp(0, 0)

def min_path_brute(tri: list):
    """Find minimum path by exploring all 2^(N-1) paths."""
    N = len(tri)
    if N == 1:
        return tri[0][0]
    best = float("inf")

    def dfs(i, j, total):
        nonlocal best
        total += tri[i][j]
        if i == N - 1:
            best = min(best, total)
            return
        dfs(i + 1, j, total)
        dfs(i + 1, j + 1, total)

    dfs(0, 0, 0)
    return best

# Solve
N = 1000
tri = make_triangle(N)
answer = min_path_dp(tri)

# Verify with top-down for medium N
tri_med = make_triangle(100)
assert min_path_dp(tri_med) == min_path_topdown(tri_med)

# Verify with brute force for small N
for test_n in [3, 5, 8, 10]:
    tri_test = make_triangle(test_n)
    assert min_path_dp(tri_test) == min_path_brute(tri_test), \
        f"N={test_n}: DP != brute"

print(answer)