LeetCode 64: Minimum Path Sum (2D DP In-Place Transition)

2026-03-17 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 64MatrixDynamic ProgrammingInterview

Today we solve LeetCode 64 - Minimum Path Sum.

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

English

Problem Summary

Given a m x n grid filled with non-negative numbers, find a path from top-left to bottom-right that minimizes the sum of all numbers along its cells. You may only move right or down.

Key Insight

Each cell (i,j) can only be reached from top (i-1,j) or left (i,j-1). So the minimum path sum to (i,j) is:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Brute Force and Limitations

DFS explores all right/down paths, which is exponential in path length. With overlapping subproblems, brute force times out quickly.

Optimal Algorithm Steps

1) Initialize first row and first column with cumulative sums.
2) For each inner cell, add current value to min(top, left).
3) Final answer is bottom-right value.

Complexity Analysis

Time: O(m*n).
Space: O(1) extra if updating grid in place (or O(m*n) for separate dp table).

Common Pitfalls

- Forgetting to precompute first row/column cumulative sums.
- Mixing up row and column bounds.
- Using recursion without memoization causing TLE.

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

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }

        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        return grid[m - 1][n - 1];
    }
}

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])

    for j := 1; j < n; j++ {
        grid[0][j] += grid[0][j-1]
    }

    for i := 1; i < m; i++ {
        grid[i][0] += grid[i-1][0]
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if grid[i-1][j] < grid[i][j-1] {
                grid[i][j] += grid[i-1][j]
            } else {
                grid[i][j] += grid[i][j-1]
            }
        }
    }

    return grid[m-1][n-1]
}

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = (int)grid.size(), n = (int)grid[0].size();

        for (int j = 1; j < n; ++j) {
            grid[0][j] += grid[0][j - 1];
        }

        for (int i = 1; i < m; ++i) {
            grid[i][0] += grid[i - 1][0];
        }

        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        return grid[m - 1][n - 1];
    }
};

from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        for j in range(1, n):
            grid[0][j] += grid[0][j - 1]

        for i in range(1, m):
            grid[i][0] += grid[i - 1][0]

        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])

        return grid[m - 1][n - 1]

var minPathSum = function(grid) {
  const m = grid.length;
  const n = grid[0].length;

  for (let j = 1; j < n; j++) {
    grid[0][j] += grid[0][j - 1];
  }

  for (let i = 1; i < m; i++) {
    grid[i][0] += grid[i - 1][0];
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
    }
  }

  return grid[m - 1][n - 1];
};

中文

题目概述

给定一个包含非负整数的 m x n 网格，从左上角走到右下角，使路径数字和最小。每一步只能向右或向下移动。

核心思路

到达每个格子 (i,j) 的上一跳只能来自上方或左方，因此状态转移为：

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

暴力解法与不足

暴力 DFS 会枚举所有“向右/向下”路径，复杂度指数级，且存在大量重复子问题，容易超时。

最优算法步骤

1）先处理第一行与第一列的前缀和。
2）遍历内部格子，将当前位置加上“上方和左方较小值”。
3）右下角即为最小路径和。

复杂度分析

时间复杂度：O(m*n)。
空间复杂度：原地修改网格时为 O(1) 额外空间（若用独立 dp 数组则为 O(m*n)）。

常见陷阱

- 忘记初始化第一行和第一列，导致转移基准错误。
- 行列边界写错（m/n 混用）。
- 纯递归不加记忆化，性能会崩。

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

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }

        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        return grid[m - 1][n - 1];
    }
}

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])

    for j := 1; j < n; j++ {
        grid[0][j] += grid[0][j-1]
    }

    for i := 1; i < m; i++ {
        grid[i][0] += grid[i-1][0]
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if grid[i-1][j] < grid[i][j-1] {
                grid[i][j] += grid[i-1][j]
            } else {
                grid[i][j] += grid[i][j-1]
            }
        }
    }

    return grid[m-1][n-1]
}

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = (int)grid.size(), n = (int)grid[0].size();

        for (int j = 1; j < n; ++j) {
            grid[0][j] += grid[0][j - 1];
        }

        for (int i = 1; i < m; ++i) {
            grid[i][0] += grid[i - 1][0];
        }

        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        return grid[m - 1][n - 1];
    }
};

from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        for j in range(1, n):
            grid[0][j] += grid[0][j - 1]

        for i in range(1, m):
            grid[i][0] += grid[i - 1][0]

        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])

        return grid[m - 1][n - 1]

var minPathSum = function(grid) {
  const m = grid.length;
  const n = grid[0].length;

  for (let j = 1; j < n; j++) {
    grid[0][j] += grid[0][j - 1];
  }

  for (let i = 1; i < m; i++) {
    grid[i][0] += grid[i - 1][0];
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
    }
  }

  return grid[m - 1][n - 1];
};