# 4ms Java DP recursive DFS solution

• ``````public class Solution {
int [][] dpTable;
public int minPathSum(int[][] grid) {
int n = grid.length -1;
int m = grid[0].length -1;
dpTable = new int [grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++){
for (int k = 0; k < grid[0].length; k++){
dpTable[i][k] = -1;
}
}
return minCost(grid, 0, 0, n, m);
}

int minCost(int[][] grid, int rowNum, int colNum, int n, int m) {
int costOfDown = 0;
int costOfRight = 0;

if(rowNum == n && colNum == m) {
return grid[rowNum][colNum];
}

if(rowNum < n) {
if (dpTable[rowNum+1][colNum] == -1) {
costOfDown = minCost(grid, rowNum+1, colNum, n, m);
dpTable[rowNum+1][colNum] = costOfDown;
}
else{
costOfDown = dpTable[rowNum+1][colNum];
}
}
else{
costOfDown = 999999; // infinity
}

if(colNum < m) {
if (dpTable[rowNum][colNum+1] == -1)
{
costOfRight = minCost(grid, rowNum, colNum+1, n, m);
dpTable[rowNum][colNum+1] = costOfRight;
}
else{
costOfRight = dpTable[rowNum][colNum+1];
}
}
else {
costOfRight = 999999; // infinity
}

return grid[rowNum][colNum] + ((costOfDown < costOfRight) ? costOfDown : costOfRight);
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.