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:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
@tag-array
Algorithm
Code
Java
-
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]); } } }
-
// 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(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]