Minimum Path Sum

medium dp grid

Problem

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Inputgrid = [[1,3,1],[1,5,1],[4,2,1]]

Output7

dp[i][j] = grid[i][j] + min(dp[i−1][j], dp[i][j−1]). Boundaries inherit from their single feasible neighbour.

grid (rows separated by ;)

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]

function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  dp[0][0] = grid[0][0];
  for (let j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
  for (let i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
  return dp[m-1][n-1];
}

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
        for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
        return dp[m-1][n-1];
    }
}

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = grid[0][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
    return dp[m-1][n-1];
}

Explanation

You walk from the top-left of a grid to the bottom-right, moving only right or down, and want the smallest sum of numbers along the way. Since you can reach any cell only from its top or left neighbour, the cheapest way in builds naturally with DP.

dp[i][j] holds the minimum total to reach cell (i, j). The general rule is dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) — add the current cell to the cheaper of the two ways you could have arrived.

The first row and first column are special: there's only one way in (straight across or straight down), so each just accumulates from its single predecessor. The answer is the value in the bottom-right corner.

Example: grid = [[1,3,1],[1,5,1],[4,2,1]]. The path 1 → 3 → 1 → 1 → 1 sums to 7, which is the minimum and ends up at dp[m-1][n-1].

Every cell is computed once from two neighbours, so the running time is O(m·n).

Time: O(m·n) Space: O(m·n) (can be reduced to O(n))