Minimum Falling Path Sum LeetCode solution in C++

1
class Solution {
2
 public:
3
  int check(int i, int j, int n) {
4
    if (i < 0 || j < 0 || i >= n || j >= n) return 0;
5
    return 1;
6
  }
7

8
  int solve(vector<vector<int>> &mat, int i, int j, int n, vector<vector<int>> &dp) {
9
    if (not check(i, j, n)) return 999999;
10

11
    if (i == n - 1 && j < n) return mat[i][j];
12

13
    if (dp[i][j] != -1) return dp[i][j];
14

15
    int op_1 = mat[i][j] + solve(mat, i + 1, j - 1, n, dp);
16
    int op_2 = mat[i][j] + solve(mat, i + 1, j, n, dp);
17
    int op_3 = mat[i][j] + solve(mat, i + 1, j + 1, n, dp);
18

19
    return dp[i][j] = min({op_1, op_2, op_3});
20
  }
21

22
  int minFallingPathSum(vector<vector<int>> &matrix) {
23
    int n = matrix[0].size();
24

25
    //         vector<vector<int>>dp(n+1 , vector<int>(n +1 , -1 ));
26
    //         int ans =  INT_MAX;
27
    //         for(int i = 0  ; i<n ; ++i )
28
    //             ans = min( ans , solve( matrix , 0, i , n , dp ));
29

30
    vector<vector<int>> dp(n, vector<int>(n, 0));
31
    for (int i = 0; i < n; ++i) dp[0][i] = matrix[0][i];
32

33
    for (int i = 1; i < n; ++i) {
34
      for (int j = 0; j < n; ++j) {
35
        if (j - 1 >= 0 && j + 1 < n)
36
          dp[i][j] = matrix[i][j] + min({dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]});
37
        else if (j == 0)
38
          dp[i][j] = matrix[i][j] + min({dp[i - 1][j], dp[i - 1][j + 1]});
39
        else if (j == n - 1)
40
          dp[i][j] = matrix[i][j] + min({dp[i - 1][j - 1], dp[i - 1][j]});
41
      }
42
    }
43

44
    int ans = INT_MAX;
45
    for (int i = 0; i < n; ++i) ans = min(ans, dp[n - 1][i]);
46

47
    return ans;
48
  }
49
};