# Different approaches: DP+O(n) space and Recursion+Memoization

• DP:

``````    public int minPathSum(int[][] m) {
for(int i=0; i<m.length; i++) {
for(int j=0;j<m[0].length; j++) {
if(i == 0 && j == 0) m[i][j] = m[i][j];
else if(i == 0) m[0][j] += m[0][j-1];
else if(j == 0) m[i][0] += m[i-1][0];
else m[i][j] = Math.min(m[i][j-1] + m[i][j], m[i-1][j] + m[i][j]);
}
}
return m[m.length-1][m[0].length-1];
}
``````

Recursion with Memoization:

``````    public int minPathSum(int[][] m) {
int[][] m1 = new int[m.length][m[0].length];
minPathSum(m, m1, 0, 0, 0);
return m1[m1.length-1][m[0].length-1];
}

private void minPathSum(int[][] m, int[][] m1, int r, int c, int sum) {
if(r > m.length-1 || c > m[0].length-1) return;
sum += m[r][c];
if(m1[r][c] != 0 && sum > m1[r][c]) return;
m1[r][c] = sum;
minPathSum(m, m1, r+1, c, sum);
minPathSum(m, m1, r, c+1, sum);
}
``````

PS: Recursive solution fails with TimeLimitExceeded. A good indication of why DP outperforms Recursive solutions.

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