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]
Lines 25 and 27 are so poorly written in the Java soln. Why not just replace them with
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid.get(i).get(j);
The javascript solution is wrong. For line 6, instead of doing for (let i = 0; i < n; i++) dp.push([...new Array(m).fill(0)]); it should be doing for (let i = 0; i < m; i++) dp.push([...new Array(n).fill(0)]);. Checking on leetcode will confirm it. This is why I use very explicit variable names like rows and cols instead of m and n where it’s easy to confuse what’s what. Also seems like this problem doesn’t have enough test cases to catch things like this.
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];
}```