Problem 82: Path Sum: Three Ways

Mathematical Foundation

Let $M$ be an $n \times n$ matrix with positive integer entries. We seek:

where a valid path starts at any $(i, 0)$, ends at any $(i', n-1)$, and uses only moves $(i,j) \to (i,j+1)$, $(i,j) \to (i-1,j)$, or $(i,j) \to (i+1,j)$.

Define $D[i][j]$ as the minimal cost to reach cell $(i,j)$ from any cell in column 0.

Lemma 1 (No vertical reversal). In any optimal path, the portion within a single column is a monotone vertical segment (purely upward or purely downward). That is, no optimal path goes up and then down (or down and then up) within the same column. Proof. Suppose an optimal path within column $j$ visits cells at rows $r_1, r_2, \ldots, r_m$ in that order, and there exist indices $a < b < c$ such that $r_a < r_b > r_c$ (a down-then-up pattern). Then the path visits some cell $(r_b, j)$ and later revisits a row between $r_a$ and $r_b$. Since all matrix entries are positive, the cost of the detour through the intermediate cells is strictly positive. Removing the detour (going directly from $r_a$ to $r_c$ via the shorter vertical path) yields a cheaper path, contradicting optimality. The argument for up-then-down is symmetric. $\square$

Theorem 1 (Two-pass correctness). The following column-by-column algorithm correctly computes $D[i][n-1]$ for all $i$:

Initialization: $D[i][0] = M[i][0]$ for all $i$.

For each column $j = 1, \ldots, n-1$:

1. Set $\mathrm{base}[i] = D[i][j-1] + M[i][j]$ for all $i$.
2. Downward pass: For $i = 1, \ldots, n-1$: $D[i][j] = \min(\mathrm{base}[i],\; D[i-1][j] + M[i][j])$.
3. Upward pass: For $i = n-2, \ldots, 0$: $D[i][j] = \min(D[i][j],\; D[i+1][j] + M[i][j])$.

Proof. By Lemma 1, any optimal path arriving at $(i,j)$ either enters directly from $(i,j-1)$, or enters from some $(k,j-1)$ and then moves purely vertically to row $i$. If $k < i$, the path moves downward from row $k$ to row $i$; the downward pass captures this by propagating costs from lower-indexed rows. If $k > i$, the path moves upward; the upward pass captures this. Since both directions are covered and vertical reversals are suboptimal, the two passes suffice.

More formally, after the downward pass, $D[i][j]$ equals the minimum cost among all paths that either enter $(i,j)$ from the left or enter some $(k,j)$ with $k \leq i$ from the left and travel down. After the upward pass, $D[i][j]$ is further minimized over paths entering from below (i.e., from $(k,j)$ with $k > i$ traveling up). Together, all cases are covered. $\square$

Theorem 2. The answer is $\min_{0 \leq i \leq n-1} D[i][n-1]$.

Proof. The problem requires the minimum over all valid paths. Since any valid path ends at some cell in column $n-1$, the global minimum is the minimum over all ending rows. $\square$

Editorial

The key observation is that when we process one column at a time, every valid path enters the new column from the left exactly once and then moves vertically within that column. Because an optimal path never reverses vertical direction inside the same column, the only possibilities are a downward sweep or an upward sweep after entering.

That is why two passes are enough. We first assume every row enters directly from the left, then propagate improvements downward to capture paths that enter higher and move down, and finally propagate improvements upward to capture paths that enter lower and move up. The candidates for each row in the current column are exactly these three forms, so after the two sweeps the column is fully optimized.

Pseudocode

Initialize the current cost for each row using the values in the leftmost column.

For each later column:
    Start a new column cost array by entering every row directly from the left

    Sweep from top to bottom:
        update each row using the possibility of coming from the row above

    Sweep from bottom to top:
        update each row using the possibility of coming from the row below

    Replace the current cost array with this optimized column

Return the smallest value in the final column.

Complexity Analysis

Time: $O(n^2)$. There are $n$ columns, and for each column the downward and upward passes each take $O(n)$ time, giving $O(n)$ per column and $O(n^2)$ total.

Space: $O(n)$. Only two arrays of length $n$ are needed: the current column’s DP values and the base array.

Answer

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

int main(){
    // Problem 82: Path Sum Three Ways
    // Minimal path sum from left column to right column,
    // moving right, up, or down.

    int n = 80;
    vector<vector<long long>> M(n, vector<long long>(n));

    ifstream fin("p082_matrix.txt");
    if(fin.is_open()){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                fin >> M[i][j];
                char ch;
                if(j < n-1) fin >> ch;
            }
        }
        fin.close();
    } else {
        n = 5;
        M = {
            {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}
        };
        // Expected for 5x5: 994
    }

    // DP column by column
    vector<long long> dp(n);
    for(int i = 0; i < n; i++)
        dp[i] = M[i][0];

    for(int j = 1; j < n; j++){
        vector<long long> ndp(n);

        // Start with cost of coming from the left
        for(int i = 0; i < n; i++)
            ndp[i] = dp[i] + M[i][j];

        // Downward pass
        for(int i = 1; i < n; i++)
            ndp[i] = min(ndp[i], ndp[i-1] + M[i][j]);

        // Upward pass
        for(int i = n-2; i >= 0; i--)
            ndp[i] = min(ndp[i], ndp[i+1] + M[i][j]);

        dp = ndp;
    }

    cout << *min_element(dp.begin(), dp.end()) << endl;
    // Full 80x80 answer: 260324

    return 0;
}

"""
Problem 82: Path Sum: Three Ways

Find the minimal path sum from the left column to the right column,
moving right, up, or down in an 80x80 matrix.

Answer: 260324
"""

import os

def solve(matrix):
    """DP column-by-column with up/down propagation."""
    n = len(matrix)
    dp = [matrix[i][0] for i in range(n)]

    for j in range(1, n):
        # Cost coming from the left
        ndp = [dp[i] + matrix[i][j] for i in range(n)]

        # Downward pass
        for i in range(1, n):
            ndp[i] = min(ndp[i], ndp[i-1] + matrix[i][j])

        # Upward pass
        for i in range(n-2, -1, -1):
            ndp[i] = min(ndp[i], ndp[i+1] + matrix[i][j])

        dp = ndp

    return min(dp)

def read_matrix(filename):
    matrix = []
    with open(filename) as f:
        for line in f:
            row = list(map(int, line.strip().split(',')))
            matrix.append(row)
    return matrix

def main():
    script_dir = os.path.dirname(os.path.abspath(__file__))
    filepath = os.path.join(script_dir, "p082_matrix.txt")

    if os.path.exists(filepath):
        matrix = read_matrix(filepath)
    else:
        matrix = [
            [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],
        ]
        # Expected: 994

    answer = solve(matrix)
    print(answer)
    # Full 80x80 answer: 260324