Recursion
import java.util.* ;
import java.io.*;
public class Solution {
public static int findCost(int [][] grid,int i,int j){
if(i==0 && j==0){
return grid[i][j];
}
if(i<0 || j<0){
return Integer.MAX_VALUE;
}
int up=findCost(grid, i-1, j);
int left=findCost(grid, i, j-1);
return grid[i][j]+Math.min(up,left);
}
public static int minSumPath(int[][] grid) {
// Write your code here.
return findCost(grid,grid.length-1,grid[0].length-1);
}
}
Memoization
import java.util.* ;
import java.io.*;
public class Solution {
public static int findCost(int [][] grid,int i,int j){
if(i==0 && j==0){
return grid[i][j];
}
if(i<0 || j<0){
return Integer.MAX_VALUE;
}
int up=Integer.MAX_VALUE;
if(i>0)
up=grid[i][j]+findCost(grid, i-1, j);
int left=Integer.MAX_VALUE;
if(j>0)
left=grid[i][j]+findCost(grid, i, j-1);
return Math.min(up,left);
}
public static int minSumPath(int[][] grid) {
// Write your code here.
return findCost(grid,grid.length-1,grid[0].length-1);
}
}
Tabulation
import java.util.* ;
import java.io.*;
public class Solution {
public static int findCost(int [][] grid,int [][] dp,int i,int j){
if(i==0 && j==0){
return dp[i][j]=grid[i][j];
}
if(i<0 || j<0){
return Integer.MAX_VALUE;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
int up=Integer.MAX_VALUE;
if(i>0)
up=grid[i][j]+findCost(grid,dp, i-1, j);
int left=Integer.MAX_VALUE;
if(j>0)
left=grid[i][j]+findCost(grid,dp, i, j-1);
return dp[i][j]=Math.min(up,left);
}
public static int minSumPath(int[][] grid) {
// Write your code here.
int m=grid.length;
int n=grid[0].length;
int dp[][]=new int [m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
dp[i][j]=-1;
}
}
return findCost(grid,dp,m-1,n-1);
}
}