Dare2Solve
Given a m x n
grid filled with non-negative numbers, find a path from the top left to the bottom right, which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.
The problem can be visualized as finding the minimum cost path in a grid where each cell has a non-negative cost. To find the optimal path, one needs to consider the cost of reaching each cell from its possible predecessors (top or left). This suggests a dynamic programming approach where we build up the solution from the smallest subproblems.
Initialization:
t
to store the minimum path sums for each cell, initialized to -1.Recursive Function:
t[m][n] != -1
), return the stored value.t
with the minimum of the sums from the top and left plus the cell's own value.Result:
O(m * n), where m
is the number of rows and n
is the number of columns in the grid. Each cell is computed only once and stored.
O(m * n) for the memoization table t
, plus the recursion stack space which can be up to O(m + n) in the worst case.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> t(m, vector<int>(n, -1));
return solve(grid, m - 1, n - 1, t);
}
private:
int solve(vector<vector<int>>& arr, int m, int n, vector<vector<int>>& t) {
if (m == 0 && n == 0) {
return arr[0][0];
} else if (m < 0 || n < 0) {
return INT_MAX;
}
if (t[m][n] != -1) {
return t[m][n];
}
int fromTop = solve(arr, m - 1, n, t);
int fromLeft = solve(arr, m, n - 1, t);
if (fromTop != INT_MAX) {
fromTop += arr[m][n];
}
if (fromLeft != INT_MAX) {
fromLeft += arr[m][n];
}
t[m][n] = min(fromTop, fromLeft);
return t[m][n];
}
};
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
t = [[-1 for _ in range(n)] for _ in range(m)]
return self.solve(grid, m - 1, n - 1, t)
def solve(self, arr: List[List[int]], m: int, n: int, t: List[List[int]]) -> int:
if m == 0 and n == 0:
return arr[0][0]
elif m < 0 or n < 0:
return float("inf")
if t[m][n] != -1:
return t[m][n]
from_top = self.solve(arr, m - 1, n, t)
from_left = self.solve(arr, m, n - 1, t)
if from_top != float("inf"):
from_top += arr[m][n]
if from_left != float("inf"):
from_left += arr[m][n]
t[m][n] = min(from_top, from_left)
return t[m][n]
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] t = new int[m][n];
// Initialize the memoization array with -1
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
t[i][j] = -1;
}
}
return solve(grid, m - 1, n - 1, t);
}
private int solve(int[][] arr, int m, int n, int[][] t) {
if (m == 0 && n == 0) {
return arr[0][0];
} else if (m < 0 || n < 0) {
return Integer.MAX_VALUE;
}
if (t[m][n] != -1) {
return t[m][n];
}
int fromTop = solve(arr, m - 1, n, t);
int fromLeft = solve(arr, m, n - 1, t);
if (fromTop != Integer.MAX_VALUE) {
fromTop += arr[m][n];
}
if (fromLeft != Integer.MAX_VALUE) {
fromLeft += arr[m][n];
}
t[m][n] = Math.min(fromTop, fromLeft);
return t[m][n];
}
}
var minPathSum = function(grid) {
let m = grid.length,n = grid[0].length
t = new Array(m+1)
for (let i = 0;i<t.length;i++){
t[i] = new Array(n+1).fill(-1)
}
let ans = solve(grid,m-1,n-1)
return ans
};
function solve(arr, m, n) {
if (m == 0 && n == 0) {
return arr[0][0]
} else if(m < 0 || n < 0) {
return Number.MAX_VALUE
}
if (t[m][n] != -1) {
return t[m][n]
}
t[m][n] = Math.min(arr[m][n]+solve(arr,m-1,n), arr[m][n]+solve(arr,m,n-1))
return t[m][n]
}