So I tried out my own method that I derived almost exactly from the robot path section. I feel like it made a lot of sense to me in terms of how it relates to the previous question, the illustration in the answer and it’s readability, is there some reason why we can’t do it like this:
dp = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
dp[0][0] = grid[0][0]
for c in range(1, len(grid)):
dp[0][c] = dp[0][c-1] + grid[0][c]
for r in range(1, len(grid[0])):
dp[r][0] += dp[r-1][0] + grid[r][0]
for r in range(1, len(grid[0])):
for c in range(1, len(grid)):
dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + grid[r][c]
return dp[-1][-1]
Hey Mido, yes, this works and cleaner!
My Java solution (uses a 2d array instead of list, so keep that in mind):
public int minPathSum(int[][] grid) {
if (grid.length == 1 && grid[0].length == 1) return grid[0][0];
int[][] dp = new int[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (i == 0 && j == 0) {
dp[i][j] = grid[i][j];
}
else if (i == 0) {
dp[i][j] = grid[i][j] + dp[i][j - 1];
}
else if (j == 0) {
dp[i][j] = grid[i][j] + dp[i - 1][j];
}
else {
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[dp.length - 1][dp[0].length - 1];
}
Bottom up for whomsoever it may concern
m = len(grid)
n = len(grid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[-1][-1] = grid[-1][-1]
for i in range(m-2, -1, -1):
dp[i][n-1] = grid[i][n-1] + dp[i+1][n-1]
for i in range(n-2, -1, -1):
dp[m-1][i] = grid[m-1][i] + dp[m-1][i+1]
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
dp[i][j] = min(dp[i+1][j], dp[i][j+1]) + grid[i][j]
return dp[0][0]
for i in range(len(grid)):
for j in range(len(grid[0])):
if j == 0 and i == 0:
continue
elif i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[-1][-1]
This is the cleanest solution.
Here’s my JS solution - it completely avoids having to prefill the first row and columns. Instead, you can prefill the dp table to Infinity and then initialize dp[0][1] and dp[1][0] to 0:
function minPathSum(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = new Array(m + 1).fill().map(_ => new Array(n + 1).fill(Infinity));
dp[0][1] = 0;
dp[1][0] = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
dp[i][j] = grid[i - 1][j - 1] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
oops - cleaned up the markdown:
function minPathSum(grid) { const m = grid.length; const n = grid[0].length; const dp = new Array(m + 1).fill().map(_ => new Array(n + 1).fill(Infinity)); dp[0][1] = 0; dp[1][0] = 0; for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { dp[i][j] = grid[i - 1][j - 1] + Math.min(dp[i - 1][j], dp[i][j - 1]); } }
return dp[m][n];
}
1 more try lol
function minPathSum(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = new Array(m + 1).fill().map(_ => new Array(n + 1).fill(Infinity));
dp[0][1] = 0;
dp[1][0] = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
dp[i][j] = grid[i - 1][j - 1] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
Space Saver
function minPathSum(grid) {
for(let r = 0; r < grid.length; r++) {
for(let c = 0; c < grid[0].length; c++) {
if(r == 0 && c === 0) continue;
if(r === 0) grid[r][c] = grid[r][c] + grid[r][c-1];
else if(c === 0) grid[r][c] = grid[r][c] + grid[r - 1][c];
else grid[r][c] = grid[r][c] + Math.min(grid[r - 1][c], grid[r][c - 1]);
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
Space Saver
function minPathSum(grid) { for(let r = 0; r < grid.length; r++) { for(let c = 0; c < grid[0].length; c++) { if(r == 0 && c === 0) continue; if(r === 0) grid[r][c] = grid[r][c] + grid[r][c-1]; else if(c === 0) grid[r][c] = grid[r][c] + grid[r - 1][c];
else grid[r][c] = grid[r][c] + Math.min(grid[r - 1][c], grid[r][c - 1]);
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
public static int minPathSum(List<List<Integer>> grid) {
// WRITE YOUR BRILLIANT CODE HERE
int[][] dp = new int[grid.size()][grid.get(0).size()];
int rLen = grid.size();
int cLen = grid.get(0).size();
int i = dp.length - 1;
for (int r = 0; r < rLen; r++){
for(int c = 0; c < cLen; c++){
int val = grid.get(r).get(c);
int prevUp = r - 1 < 0 ? Integer.MAX_VALUE : dp[r-1][c];
int prevRight = c - 1 < 0 ? Integer.MAX_VALUE : dp[r][c - 1];
dp[r][c] = prevRight == Integer.MAX_VALUE && prevUp == Integer.MAX_VALUE ? val : Math.min(prevUp,prevRight) + val;
count++;
}
}
return dp[i][i];
}```my top-down solution. sharing with you guys
from math import inf
def min_path_sum(grid: List[List[int]]) -> int:
def dfs(x, y, memo):
if memo[x][y] != -1:
return memo[x][y]
if x == len(grid) - 1 and y == len(grid[0]) - 1:
return grid[x][y]
down, right = inf, inf
if x + 1 <= len(grid) - 1:
right = dfs(x + 1, y, memo) + grid[x][y]
if y + 1 <= len(grid[0]) - 1:
down = dfs(x, y + 1, memo) + grid[x][y]
result = min(down, right)
memo[x][y] = result
return result
memo = [[-1 for y in range(len(grid[0]))] for x in range(len(grid))]
return dfs(0, 0, memo)