java_leetcode/Minimum_Falling_Path_Sum_II.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
import java.util.*;
import java.io.*;
import java.lang.*;
public class Minimum_Falling_Path_Sum_II {
    class Solution {
        public int minFallingPathSum(int[][] grid)
        {
            int n = grid.length, m = grid[0].length;
            int res = Integer.MAX_VALUE;
            int[][] dp = new int[n][m];
            for(int row[] : dp)
            {
                Arrays.fill(row, -1);
            }

            for(int j = 0; j < m; ++j)
            {
                dp[0][j] = grid[0][j];
            }

            for(int i = 1; i < n; ++i)
            {
                for(int j = 0; j < m; ++j)
                {
                    int temp = Integer.MAX_VALUE;
                    for(int k = 0; k < m; ++k)
                    {
                        if(j != k)
                        {
                            temp = Math.min(temp, grid[i][j] + dp[i - 1][k]);
                        }
                        dp[i][j] = temp;
                    }
                }
            }
            for(int j = 0; j < m; ++j)
            {
                res = Math.min(res, dp[n - 1][j]);
            }
            return res;
        }
    }


// Recurssion

// class Solution {
//     public int minFallingPathSum(int[][] grid)
//     {
//         return minFallingPathSumRecursive(grid, 0, -1);
//     }
//     private int minFallingPathSumRecursive(int[][] grid, int row, int prevCol)
//     {
//         if(row == grid.length - 1)
//         {
//             int min = Integer.MAX_VALUE;
//             for(int col = 0; col < grid[row].length; col++)
//             {
//                 if(col != prevCol)
//                 {
//                     min = Math.min(min, grid[row][col]);
//                 }
//             }
//             return min;
//         }
//         int minFallingPathSum = Integer.MAX_VALUE;
//         for(int col = 0; col < grid[row].length; col++)
//         {
//             if(col != prevCol)
//             {
//                 int fallingPathSum = minFallingPathSumRecursive(grid, row + 1, col) + grid[row][col];
//                 minFallingPathSum = Math.min(minFallingPathSum, fallingPathSum);
//             }
//         }
//         return minFallingPathSum;
//     }
// }


// class Solution {
//     public int minFallingPathSum(int[][] grid)
//     {
//         int n = grid.length;
//         int m = grid[0].length;
//         int min = 99999999;
//         for(int i = 0 ; i<m ; i++)
//         {
//             int a = fun(0 , i , -1 , grid);
//             min = Math.min(min , a);
//         }
//         return min;
//     }

//     public int fun(int r , int c , int last , int[][] grid)
//     {
//         if(r==grid.length-1)
//         {
//             return grid[r][c];
//         }
//         int mini = 99999999;
//         for(int i = 0 ; i<grid.length ; i++)
//         {
//             if(last!=i)
//             {
//                 int b = fun(r+1 , i , c , grid) + grid[r][c];
//                 mini = Math.min(mini , b);
//             }
//         }
//         return mini;
//     }
// }
}