java_leetcode/Minimum_Falling_Path_Sum.java at master · kumarvvijay059/java_leetcode · 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import java.io.*;
import java.lang.*;
import java.util.*;
public class Minimum_Falling_Path_Sum {
    class Solution {

        //DP Tabulation
        public int minFallingPathSum(int[][] matrix) {
            int n = matrix.length;
            int m = matrix[0].length;
            int[][] dp = new int[n][m];
            for(int i = 0 ; i<m ; i++)
            {
                dp[0][i] = matrix[0][i];
            }
            for(int i = 1 ; i<n ; i++)
            {
                for(int j = 0 ; j<m ; j++)
                {
                    int down = matrix[i][j] + dp[i-1][j];
                    int down_l = Integer.MAX_VALUE;
                    int down_r = Integer.MAX_VALUE;
                    if(j-1>=0)
                    {
                        down_l = matrix[i][j] + dp[i-1][j-1];
                    }
                    if(j+1<m)
                    {
                        down_r = matrix[i][j] + dp[i-1][j+1];
                    }
                    dp[i][j] = Math.min(down , Math.min(down_l , down_r));
                }
            }
            int min = Integer.MAX_VALUE;
            for(int i = 0 ; i<m ; i++)
            {
                if(min>dp[n-1][i])
                {
                    min = dp[n-1][i];
                }
            }
            return min;
        }


        //DP Memoization

        // public int minFallingPathSum(int[][] matrix) {
        //     int n = matrix.length;
        //     int m = matrix[0].length;
        //     int[][] dp = new int[n][m];
        //     for(int rows[] : dp)
        //     {
        //         Arrays.fill(rows , -1);
        //     }
        //     int min = Integer.MAX_VALUE;
        //     for(int i = 0 ; i<m ; i++)
        //     {
        //         int mini = fun(matrix , n , m , 0 , i , dp);
        //         if(min>mini)
        //         {
        //             min = mini;
        //         }
        //     }
        //     return min;
        // }

        // public static int fun(int[][] matrix , int r , int c , int row , int col , int[][] dp)
        // {
        //     if(col<0 || col>=c)
        //     {
        //         return (int)1e5;
        //     }
        //     if(row == r-1)
        //     {
        //         return matrix[row][col];
        //     }
        //     if(dp[row][col] != -1)
        //     {
        //         return dp[row][col];
        //     }
        //     int down = matrix[row][col] + fun(matrix , r , c , row+1 , col , dp);
        //     int down_l = matrix[row][col] + fun(matrix , r , c , row+1 , col-1 , dp);
        //     int down_r = matrix[row][col] + fun(matrix , r , c , row+1 , col+1 , dp);
        //     int min = Math.min(down , Math.min(down_l , down_r));
        //     return dp[row][col] = min;
        // }


        // Recursion

        // public int minFallingPathSum(int[][] matrix) {
        //     int n = matrix.length;
        //     int m = matrix[0].length;
        //     int min = Integer.MAX_VALUE;
        //     for(int i = 0 ; i<m ; i++)
        //     {
        //         int mini = fun(matrix , n , m , 0 , i);
        //         if(min>mini)
        //         {
        //             min = mini;
        //         }
        //     }
        //     return min;
        // }

        // public static int fun(int[][] matrix , int r , int c , int row , int col)
        // {
        //     if(col<0 || col>=c)
        //     {
        //         return (int)1e5;
        //     }
        //     if(row == r-1)
        //     {
        //         return matrix[row][col];
        //     }
        //     int down = matrix[row][col] + fun(matrix , r , c , row+1 , col);
        //     int down_l = matrix[row][col] + fun(matrix , r , c , row+1 , col-1);
        //     int down_r = matrix[row][col] + fun(matrix , r , c , row+1 , col+1);
        //     int min = Math.min(down , Math.min(down_l , down_r));
        //     return min;
        // }
    }
}