Problem 81: Path Sum: Two Ways

Mathematical Foundation

Let $M$ be an $n \times n$ matrix (with $n = 80$) where $M[i][j]$ denotes the value at row $i$, column $j$ (0-indexed). A valid path is a sequence of cells $(c_0, c_1, \ldots, c_{2(n-1)})$ with $c_0 = (0,0)$, $c_{2(n-1)} = (n-1,n-1)$, and each step $c_{t+1} - c_t \in \{(0,1),(1,0)\}$. The cost of a path is $\sum_{t} M[c_t]$.

Define $D[i][j]$ as the minimal cost of any valid path from $(0,0)$ to $(i,j)$.

Lemma 1. Every valid path from $(0,0)$ to $(n-1,n-1)$ consists of exactly $n-1$ right moves and $n-1$ down moves, visiting exactly $2n-1$ cells. Proof. Each right move increments the column index by 1 and each down move increments the row index by 1. To go from column 0 to column $n-1$ requires exactly $n-1$ right moves; similarly for rows. The path visits the starting cell plus one cell per move, totaling $1 + 2(n-1) = 2n-1$ cells. $\square$

Lemma 2. The number of valid paths is $\binom{2(n-1)}{n-1}$. Proof. A valid path is uniquely determined by choosing which $n-1$ of the $2(n-1)$ steps are right moves (the remainder are down moves). $\square$

Theorem 1 (Optimal Substructure). The recurrence

correctly computes $D[n-1][n-1]$ as the minimum path cost.

Proof. By strong induction on $k = i + j$.

Base case ($k=0$): The only cell with $i+j=0$ is $(0,0)$, and $D[0][0] = M[0][0]$ is trivially the minimum cost to reach $(0,0)$.

Inductive step: Assume $D[i'][j']$ equals the true minimum cost for all $(i',j')$ with $i'+j' < k$. Consider a cell $(i,j)$ with $i+j = k$. Any valid path from $(0,0)$ to $(i,j)$ must arrive via the penultimate cell, which is either $(i-1,j)$ (if $i \geq 1$) or $(i,j-1)$ (if $j \geq 1$). If $i = 0$, the path can only come from $(0,j-1)$, so $D[0][j] = D[0][j-1] + M[0][j]$. Similarly for $j = 0$. In the general case ($i,j \geq 1$), the optimal path to $(i,j)$ costs $M[i][j]$ plus the minimum of the optimal costs to reach $(i-1,j)$ and $(i,j-1)$, both of which are correctly computed by the inductive hypothesis. Thus $D[i][j] = M[i][j] + \min(D[i-1][j], D[i][j-1])$ is correct. $\square$

Editorial

Because the movement is restricted to the right and downward directions, every path to a cell must end by entering from exactly one of two places: the cell above it or the cell to its left. That makes the problem a clean dynamic program on an acyclic grid.

The first row and first column are forced, since there is only one way to reach those cells. After that, every interior cell simply takes its own value plus the cheaper of its two admissible predecessors. The candidates are therefore generated locally from the allowed moves, and the move restriction itself is what keeps the recurrence complete and correct.

Pseudocode

Read the matrix and create a table of the same size for minimal path costs.

Set the starting cell to the value in the top-left corner.

Fill the first row by accumulating values from left to right.
Fill the first column by accumulating values from top to bottom.

For each remaining cell:
    Compute the cost of arriving from above
    Compute the cost of arriving from the left
    Store the cell value plus the smaller of those two costs

Return the value stored in the bottom-right corner.

Complexity Analysis

Time: $O(n^2)$. The algorithm fills an $n \times n$ table, computing each entry in $O(1)$ (one addition and one comparison). The total number of operations is $n^2$.

Space: $O(n^2)$ for the full DP table. This can be reduced to $O(n)$ by observing that computing row $i$ requires only row $i-1$, so a single rolling array suffices.

Answer

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

int main(){
    // Problem 81: Path Sum Two Ways
    // Reads an 80x80 matrix from "p081_matrix.txt" (comma-separated)
    // and finds the minimal path sum from top-left to bottom-right
    // moving only right and down.
    //
    // If the input file is not available, we use a small example
    // and print the expected answer for the full problem.

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

    ifstream fin("p081_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; // consume comma
            }
        }
        fin.close();
    } else {
        // Example 5x5 matrix from Project Euler
        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 answer for 5x5: 2427
    }

    // DP
    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    dp[0][0] = M[0][0];

    // First row
    for(int j = 1; j < n; j++)
        dp[0][j] = dp[0][j-1] + M[0][j];

    // First column
    for(int i = 1; i < n; i++)
        dp[i][0] = dp[i-1][0] + M[i][0];

    // Fill rest
    for(int i = 1; i < n; i++)
        for(int j = 1; j < n; j++)
            dp[i][j] = M[i][j] + min(dp[i-1][j], dp[i][j-1]);

    cout << dp[n-1][n-1] << endl;
    // Full 80x80 answer: 427337

    return 0;
}

"""
Problem 81: Path Sum: Two Ways

Find the minimal path sum from top-left to bottom-right of an 80x80 matrix,
moving only right and down.

Answer: 427337
"""

import os
import sys

def solve(matrix):
    """DP solution for minimal path sum (right and down only)."""
    n = len(matrix)
    dp = [[0]*n for _ in range(n)]
    dp[0][0] = matrix[0][0]

    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + matrix[0][j]
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + matrix[i][0]
    for i in range(1, n):
        for j in range(1, n):
            dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i][j-1])

    return dp[n-1][n-1]

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():
    # Try to read the actual matrix file
    script_dir = os.path.dirname(os.path.abspath(__file__))
    filepath = os.path.join(script_dir, "p081_matrix.txt")

    if os.path.exists(filepath):
        matrix = read_matrix(filepath)
    else:
        # Example 5x5 matrix from Project Euler problem description
        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: 2427 for this example

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