Minimum Falling Path Sum

medium array dp matrix

Problem

Given an n×n grid, return the minimum sum of any falling path. From cell (r, c) you may step to (r+1, c-1), (r+1, c), or (r+1, c+1).

Inputmatrix = [[2,1,3],[6,5,4],[7,8,9]]

Output13

DP from the top: dp[r][c] = matrix[r][c] + min(dp[r-1][c-1..c+1]).

matrix (rows separated by ';')

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = [row[:] for row in matrix]
    for r in range(1, n):
        for c in range(n):
            best = dp[r - 1][c]
            if c > 0: best = min(best, dp[r - 1][c - 1])
            if c < n - 1: best = min(best, dp[r - 1][c + 1])
            dp[r][c] += best
    return min(dp[-1])

function minFallingPathSum(matrix) {
  const n = matrix.length;
  const dp = matrix.map(r => r.slice());
  for (let r = 1; r < n; r++) {
    for (let c = 0; c < n; c++) {
      let best = dp[r - 1][c];
      if (c > 0) best = Math.min(best, dp[r - 1][c - 1]);
      if (c < n - 1) best = Math.min(best, dp[r - 1][c + 1]);
      dp[r][c] += best;
    }
  }
  return Math.min(...dp[n - 1]);
}

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i] = matrix[i].clone();
        for (int r = 1; r < n; r++) {
            for (int c = 0; c < n; c++) {
                int best = dp[r - 1][c];
                if (c > 0) best = Math.min(best, dp[r - 1][c - 1]);
                if (c < n - 1) best = Math.min(best, dp[r - 1][c + 1]);
                dp[r][c] += best;
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int v : dp[n - 1]) ans = Math.min(ans, v);
        return ans;
    }
}

int minFallingPathSum(vector<vector<int>>& matrix) {
    int n = (int)matrix.size();
    auto dp = matrix;
    for (int r = 1; r < n; r++) {
        for (int c = 0; c < n; c++) {
            int best = dp[r - 1][c];
            if (c > 0) best = min(best, dp[r - 1][c - 1]);
            if (c < n - 1) best = min(best, dp[r - 1][c + 1]);
            dp[r][c] += best;
        }
    }
    return *min_element(dp[n - 1].begin(), dp[n - 1].end());
}

Explanation

A falling path starts anywhere in the top row and, from cell (r, c), drops to one of three cells just below: straight down or one step diagonally. We want the cheapest such path, and DP builds it up row by row.

We copy the matrix into dp and process from the second row down. Each dp[r][c] becomes its own value plus the minimum of the up-to-three reachable cells above: dp[r-1][c-1], dp[r-1][c], and dp[r-1][c+1] (skipping any that fall off the edge).

By the time we finish a row, every cell holds the cheapest cost to reach it from the top. The final answer is simply the minimum of the last row, since a path may end at any bottom column.

Example: matrix = [[2,1,3],[6,5,4],[7,8,9]]. Following 1 → 4 → ... style diagonal moves, the cheapest top-to-bottom total comes out to 13.

Each cell looks at a constant number of neighbours, so the whole grid is filled in O(n²) time.

Time: O(n²) Space: O(n²)