dp_coding_ninja/Minimum_Path_Sum.java at master · kumarvvijay059/dp_coding_ninja · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.* ;
import java.io.*;

public class Minimum_Path_Sum {

    // Memoization dp
    public class Solution {
        public static int minSumPath(int[][] grid) {
            int n = grid.length;
            int m = grid[0].length;
            int[][] dp = new int[n][m];
            for(int[] rows : dp)
            {
                Arrays.fill(rows , -1);
            }
            return (int)pathSum(grid , n , m , 0 , 0 , dp);
        }

        public static long pathSum(int[][] grid, int n, int m, int r, int c , int[][] dp)
        {
            if (r == n - 1 && c == m - 1)
            {
                return grid[r][c];
            }
            if (r >= n || c >= m)
            {
                return Integer.MAX_VALUE;
            }
            if(dp[r][c]!=-1)
            {
                return dp[r][c];
            }
            long path_d = grid[r][c] + pathSum(grid, n, m, r + 1, c , dp);
            long path_r = grid[r][c] + pathSum(grid, n, m, r, c + 1 , dp);
            long min = Math.min(path_d, path_r);
            return dp[r][c] = (int)min;
        }
    }

// Recurrsion
// public class Solution {
//     public static int minSumPath(int[][] grid) {
//         int n = grid.length;
//         int m = grid[0].length;
//     	return (int)pathSum(grid , n , m , 0 , 0);
//     }

//     public static long pathSum(int[][] grid, int n, int m, int r, int c)
//     {
//         if (r == n - 1 && c == m - 1)
//         {
//             return grid[r][c];
//         }
//         if (r >= n || c >= m)
//         {
//             return Integer.MAX_VALUE;
//         }
//         long path_d = grid[r][c] + pathSum(grid, n, m, r + 1, c);
//         long path_r = grid[r][c] + pathSum(grid, n, m, r, c + 1);
//         long min = Math.min(path_d, path_r);
//         return min;
//     }
// }


}