Minimum Path Sum

Problem Statement

You’re navigating a grid from top-left to bottom-right, moving only right or down. Each cell has a cost. Find the minimum sum path. This medium-level DP journey is a treasure map—find the cheapest route!

Example

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

Output: 7 (1→3→1→1→1)

Input: grid = [[1,2],[3,4]]

Output: 7 (1→2→4)

Input: grid = [[1]]

Output: 1

Code

public 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 i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][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++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}
            

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 i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    return dp[m-1][n-1]

# Example usage
print(min_path_sum([[1,3,1],[1,5,1],[4,2,1]]))  # 7
print(min_path_sum([[1,2],[3,4]]))  # 7
            

function minPathSum(grid) {
    let m = grid.length, n = grid[0].length;
    let dp = Array(m).fill().map(() => Array(n).fill(0));
    dp[0][0] = grid[0][0];
    for (let i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][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++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

// Example usage
console.log(minPathSum([[1,3,1],[1,5,1],[4,2,1]]));  // 7
console.log(minPathSum([[1,2],[3,4]]));  // 7
            

Explanation

• DP Insight: dp[i][j] = min cost to reach (i,j).
• Steps: Fill edges first, then min of up or left plus current cost.
• Flow Example ([[1,3,1],[1,5,1]]): dp[0][2]=5, dp[1][2]=7 (1→3→1→1).
• Why It Works: Builds shortest path incrementally.

Note