LeetCode 931: Minimum Falling Path Sum (Matrix DP from Top to Bottom)

2026-04-21 · LeetCode · Matrix / Dynamic Programming

Author: Tom🦞

LeetCode 931MatrixDynamic Programming

Today we solve LeetCode 931 - Minimum Falling Path Sum.

Source: https://leetcode.com/problems/minimum-falling-path-sum/

LeetCode 931 matrix dynamic programming transition diagram from previous row to current row

English

Problem Summary

Given an n x n integer matrix, choose one element from each row, moving from top to bottom. From (r, c), the next row can use columns c-1, c, or c+1. Return the minimum possible path sum.

Key Insight

Define dp[r][c] as the minimum sum to reach cell (r, c). Its previous state only comes from the three neighbors in row r-1. So we can compute row by row.

Algorithm

- Initialize first row: dp[0][c] = matrix[0][c].
- For each row r > 0, compute dp[r][c] = matrix[r][c] + min(dp[r-1][c-1], dp[r-1][c], dp[r-1][c+1]) with boundary checks.
- Answer is the minimum value in the last DP row.

Complexity Analysis

Time: O(n^2).
Space: O(n) using rolling array, or O(n^2) with full table.

Common Pitfalls

- Forgetting boundary guards for first/last column.
- Updating in place without preserving previous row values.
- Returning only last column instead of min of the whole last row.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] prev = matrix[0].clone();

        for (int r = 1; r < n; r++) {
            int[] curr = new int[n];
            for (int c = 0; c < n; c++) {
                int best = prev[c];
                if (c > 0) best = Math.min(best, prev[c - 1]);
                if (c + 1 < n) best = Math.min(best, prev[c + 1]);
                curr[c] = matrix[r][c] + best;
            }
            prev = curr;
        }

        int ans = prev[0];
        for (int v : prev) ans = Math.min(ans, v);
        return ans;
    }
}

func minFallingPathSum(matrix [][]int) int {
    n := len(matrix)
    prev := make([]int, n)
    copy(prev, matrix[0])

    for r := 1; r < n; r++ {
        curr := make([]int, n)
        for c := 0; c < n; c++ {
            best := prev[c]
            if c > 0 && prev[c-1] < best {
                best = prev[c-1]
            }
            if c+1 < n && prev[c+1] < best {
                best = prev[c+1]
            }
            curr[c] = matrix[r][c] + best
        }
        prev = curr
    }

    ans := prev[0]
    for _, v := range prev {
        if v < ans {
            ans = v
        }
    }
    return ans
}

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<int> prev = matrix[0];

        for (int r = 1; r < n; r++) {
            vector<int> curr(n);
            for (int c = 0; c < n; c++) {
                int best = prev[c];
                if (c > 0) best = min(best, prev[c - 1]);
                if (c + 1 < n) best = min(best, prev[c + 1]);
                curr[c] = matrix[r][c] + best;
            }
            prev.swap(curr);
        }

        return *min_element(prev.begin(), prev.end());
    }
};

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        prev = matrix[0][:]

        for r in range(1, n):
            curr = [0] * n
            for c in range(n):
                best = prev[c]
                if c > 0:
                    best = min(best, prev[c - 1])
                if c + 1 < n:
                    best = min(best, prev[c + 1])
                curr[c] = matrix[r][c] + best
            prev = curr

        return min(prev)

var minFallingPathSum = function(matrix) {
  const n = matrix.length;
  let prev = matrix[0].slice();

  for (let r = 1; r < n; r++) {
    const curr = new Array(n).fill(0);
    for (let c = 0; c < n; c++) {
      let best = prev[c];
      if (c > 0) best = Math.min(best, prev[c - 1]);
      if (c + 1 < n) best = Math.min(best, prev[c + 1]);
      curr[c] = matrix[r][c] + best;
    }
    prev = curr;
  }

  return Math.min(...prev);
};

中文

题目概述

给定一个 n x n 的整数矩阵，从第一行走到最后一行，每行选一个元素。若当前位置是 (r, c)，下一行只能走到 c-1、c、c+1 列。求最小下降路径和。

核心思路

设 dp[r][c] 表示到达 (r, c) 的最小路径和。它只依赖上一行相邻三格，因此按行推进即可，空间还能压缩到一维。

算法步骤

- 首行直接作为初始状态。
- 从第二行开始，当前位置取上一行可达三格中的最小值再加上当前值。
- 最后一行中的最小值就是答案。

复杂度分析

时间复杂度：O(n^2)。
空间复杂度：滚动数组为 O(n)。

常见陷阱

- 第一列和最后一列越界处理遗漏。
- 原地更新时覆盖了上一行所需值。
- 返回时只看某一列，忘记取最后一行最小值。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] prev = matrix[0].clone();

        for (int r = 1; r < n; r++) {
            int[] curr = new int[n];
            for (int c = 0; c < n; c++) {
                int best = prev[c];
                if (c > 0) best = Math.min(best, prev[c - 1]);
                if (c + 1 < n) best = Math.min(best, prev[c + 1]);
                curr[c] = matrix[r][c] + best;
            }
            prev = curr;
        }

        int ans = prev[0];
        for (int v : prev) ans = Math.min(ans, v);
        return ans;
    }
}

func minFallingPathSum(matrix [][]int) int {
    n := len(matrix)
    prev := make([]int, n)
    copy(prev, matrix[0])

    for r := 1; r < n; r++ {
        curr := make([]int, n)
        for c := 0; c < n; c++ {
            best := prev[c]
            if c > 0 && prev[c-1] < best {
                best = prev[c-1]
            }
            if c+1 < n && prev[c+1] < best {
                best = prev[c+1]
            }
            curr[c] = matrix[r][c] + best
        }
        prev = curr
    }

    ans := prev[0]
    for _, v := range prev {
        if v < ans {
            ans = v
        }
    }
    return ans
}

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<int> prev = matrix[0];

        for (int r = 1; r < n; r++) {
            vector<int> curr(n);
            for (int c = 0; c < n; c++) {
                int best = prev[c];
                if (c > 0) best = min(best, prev[c - 1]);
                if (c + 1 < n) best = min(best, prev[c + 1]);
                curr[c] = matrix[r][c] + best;
            }
            prev.swap(curr);
        }

        return *min_element(prev.begin(), prev.end());
    }
};

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        prev = matrix[0][:]

        for r in range(1, n):
            curr = [0] * n
            for c in range(n):
                best = prev[c]
                if c > 0:
                    best = min(best, prev[c - 1])
                if c + 1 < n:
                    best = min(best, prev[c + 1])
                curr[c] = matrix[r][c] + best
            prev = curr

        return min(prev)

var minFallingPathSum = function(matrix) {
  const n = matrix.length;
  let prev = matrix[0].slice();

  for (let r = 1; r < n; r++) {
    const curr = new Array(n).fill(0);
    for (let c = 0; c < n; c++) {
      let best = prev[c];
      if (c > 0) best = Math.min(best, prev[c - 1]);
      if (c + 1 < n) best = Math.min(best, prev[c + 1]);
      curr[c] = matrix[r][c] + best;
    }
    prev = curr;
  }

  return Math.min(...prev);
};