“I recently found a frustrating error in my code. I have two solutions for finding the minimum path sum using dynamic programming (DP). The first solution, which I wrote, doesn’t seem to work, even though the logic seems perfect. Here’s my code:
class Solution {
public int minPathSum(int[][] arr) {
return f(arr.length-1, arr[0].length-1, arr);
}
public int f(int i, int j, int[][] arr) {
if (i < 0 || j < 0) return Integer.MAX_VALUE;
if (i == 0 && j == 0) return arr[0][0];
int up = arr[i][j] + f(i-1, j, arr);
int left = arr[i][j] + f(i, j-1, arr);
return Math.min(up, left);
}
}
However, I found another solution online that works:
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length-1;
int n = grid[0].length-1;
return find(grid, m, n);
}
public int find(int grid[][], int m, int n) {
if (m < 0 || n < 0) return Integer.MAX_VALUE;
if (m == 0 && n == 0) return grid[0][0];
return grid[m][n] + Math.min(find(grid, m-1, n), find(grid, m, n-1));
}
}
The only difference between my solution and the working solution is how we return the result. In my solution, I used up
and left
to store the result of recursive calls with the current path value, and later chose the minimum path. However, in the working solution, it’s all done in a single step. What’s the difference between these two? Please clarify my doubt.”
Suryanarayanan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.