Welcome to Subscribe On Youtube
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.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
Algorithm
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] } }