# Question

Formatted question description: https://leetcode.ca/all/64.html

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.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

# Code

• 
public class Minimum_Path_Sum {

public static void main (String[] args) {
Minimum_Path_Sum out = new Minimum_Path_Sum();
Solution_recursion s = out.new Solution_recursion();

System.out.println(s.minPathSum(new int[][]{ {1,3,1}, {1,5,1}, {4,2,1} }));
}

public class Solution {
public int minPathSum(int[][] grid) {

if (grid.length == 0 || grid[0].length == 0) {
return 0;
}

int m = grid.length;
int n = grid[0].length;

// dp[i][j] meaning min-sum at (i,j)
int[][] dp = new int[m][n];

dp[0][0] = grid[0][0];

// pre-process, first row and col
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];
}

}

class Solution_recursion {

int min = Integer.MAX_VALUE;

public int minPathSum(int[][] grid) {

if (grid == null || grid.length == 0 || grid[0].length == 0) {
return -1;
}

dfs (grid, 0, 0, 0);
return min;
}

private void dfs(int[][] grid, int i, int j, int sum) {

if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
// out of boundary
return;
}

if (i == grid.length - 1 && j == grid[0].length - 1) {
// reaching termination position
min = Math.min(sum + grid[i][j], min);
}

dfs(grid, i + 1, j, sum + grid[i][j]);
dfs(grid, i, j + 1, sum + grid[i][j]);

// actually, if detour is allowed, then should probe for all 4 directions, since maybe there is a Ingeter.MIN value
//			dfs(grid, i + 1, j, sum + grid[i][j]);
//			dfs(grid, i + 1, j, sum + grid[i][j]);
}

}

}

############

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];
}
}

• // OJ: https://leetcode.com/problems/minimum-path-sum/
// Time: O(MN)
// Space: O(1)
class Solution {
public:
int minPathSum(vector<vector<int>>& A) {
int M = A.size(), N = A[0].size();
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
int sum = min(i - 1 >= 0 ? A[i - 1][j] : INT_MAX, j - 1 >= 0 ? A[i][j - 1] : INT_MAX);
A[i][j] += sum == INT_MAX ? 0 : sum;
}
}
return A[M - 1][N - 1];
}
};

• class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[grid[0][0]] * n for _ in range(m)]
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[-1][-1]

############

class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if len(grid) == 0:
return 0
dp = [0 for _ in range(0, len(grid[0]))]
dp[0] = grid[0][0]

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

for i in range(1, len(grid)):
pre = dp[0] + grid[i][0]
for j in range(1, len(grid[0])):
dp[j] = min(dp[j], pre) + grid[i][j]
pre = dp[j]
dp[0] += grid[i][0]

return dp[-1]


• func minPathSum(grid [][]int) int {
m, n := len(grid), len(grid[0])
dp := make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
}
dp[0][0] = grid[0][0]
for i := 1; i < m; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
for j := 1; j < n; j++ {
dp[0][j] = dp[0][j-1] + grid[0][j]
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
}
}
return dp[m-1][n-1]
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

• function minPathSum(grid: number[][]): number {
let m = grid.length,
n = grid[0].length;
let dp = Array.from({ length: m }, v => new 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];
}


• /**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function (grid) {
let m = grid.length,
n = grid[0].length;
let dp = Array.from({ length: m }, v => new 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];
};


• 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];
}
}

• impl Solution {
pub fn min_path_sum(mut grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
for i in 1..m {
grid[i][0] += grid[i - 1][0];
}
for i in 1..n {
grid[0][i] += grid[0][i - 1];
}
for i in 1..m {
for j in 1..n {
grid[i][j] += grid[i][j - 1].min(grid[i - 1][j]);
}
}
grid[m - 1][n - 1]
}
}