Algorithm
Problem Name: 64. Minimum Path Sum
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.
Note: You can only move either down or right at any point in time.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1,2,3],[4,5,6]] Output: 12
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
int minPathSum(int **grid, int nRows, int nCols) {
int i, j;
for (i = 0; i < nRows; i++) {
for (j = 0; j < nCols; j++) {
if (i > 0 && j == 0)
grid[i][j] += grid[i - 1][j];
if (j > 0 && i == 0)
grid[i][j] += grid[i][j - 1];
if (i > 0 && j > 0) {
if (grid[i][j - 1] < grid[i - 1][j])
grid[i][j] += grid[i][j - 1];
else
grid[i][j] += grid[i - 1][j];
}
}
}
/*
for (i = 0; i < nRows; i++) {
for (j = 0; j < nCols; j++) {
printf("%d ", grid[i][j]);
}
printf("\n");
}
*/
return grid[nRows - 1][nCols - 1];
}
int main() {
int m, n, i;
m = n = 3;
int **grid = (int **) calloc (m, sizeof(int *));
for (i = 0; i < m; i++)
grid[i] = (int *) calloc (n, sizeof(int));
grid[0][0] = 1; grid[0][1] = 2; grid[0][2] = 3;
grid[1][0] = 1; grid[1][1] = 2; grid[1][2] = 3;
grid[2][0] = 1; grid[2][1] = 2; grid[2][2] = 3;
printf("%d\n", minPathSum(grid, m, n));
return 0;
}
Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.empty()) return 0;
int m = grid.size(), n = grid[0].size();
vector<vector < int>>dp(m, vector<int>(n));
dp[0][0] = grid[0][0];
for(int i = 1; i < m; i++) dp[i][0] = grid[i][0] + dp[i - 1][0];
for(int i = 1; i < n; i++) dp[0][i] = grid[0][i] + dp[0][i - 1];
for(int i = 1; i < m; i++)
for(int j = 1; j < n; j++)
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]> + grid[i][j];
return dp[m - 1][n - 1];
}
};
Input
grid = [[1,2,3],[4,5,6]]
Output
12
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[i].length; j++) {
dp[i][j] += grid[i][j];
if (i > 0 && j > 0) {
dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1]);
} else if (i > 0) {
dp[i][j] += dp[i - 1][j];
} else if (j > 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
return dp[grid.length - 1][grid[0].length - 1];
}
}
Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const minPathSum = function(grid) {
const m = grid.length;
const n = grid[0].length;
for (let i = 1; i < n; i++) {
grid[0][i] += grid[0][i - 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];
};
Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
for i in range(len(grid)):
for j in range(len(grid[0])):
grid[i][j] += min(grid[i][j - 1] if j > 0 else float("inf"), grid[i - 1][j] if i > 0 else float("inf")) if i!=0 or j != 0 else 0
return grid[-1][-1]
Input
grid = [[1,2,3],[4,5,6]]
Output
12
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _064_MinimumPathSum
{
public int MinPathSum(int[][] grid)
{
var rowLenght = grid.Length;
var columnLenght = grid[0].Length;
var pathSum = new int[columnLenght];
for (int i = 0; i < columnLenght; i++)
pathSum[i] = int.MaxValue;
pathSum[0] = 0;
for (int i = 0; i < rowLenght; i++)
{
pathSum[0] += grid[i][0];
for (int j = 1; j < columnLenght; j++)
pathSum[j] = Math.Min(pathSum[j - 1], pathSum[j]) + grid[i][j];
}
return pathSum[columnLenght - 1];
}
}
}
Input
grid = [[1,2,3],[4,5,6]]
Output
12