Minimum Falling Path Sum II LeetCode solution in C++

1
class Solution {
2
 public:
3
  int f(int i, int j, vector<vector<int>> &matrix, vector<vector<int>> &dp) {
4
    // to handle edge cases if the j index is less than 0 or greater than size
5
    // of the array.
6
    if (j < 0 or j >= matrix[0].size()) return 1e8;
7

8
    // base case
9
    if (i == 0) return dp[0][j] = matrix[0][j];
10

11
    if (dp[i][j] != -1) return dp[i][j];
12

13
    int ans = INT_MAX;
14

15
    // Here we have to iterate through all the possiblities in the entire upper
16
    // row for each element except for the element which is directly above the
17
    // current element in the matrix, and then we have to find the minimum.
18
    for (int k = 0; k < matrix[0].size(); k++) {
19
      if (k == j) continue;
20
      ans = min(ans, matrix[i][j] + f(i - 1, k, matrix, dp));
21
    }
22

23
    return dp[i][j] = ans;
24
  }
25

26
  int minFallingPathSum(vector<vector<int>> &grid) {
27
    int mini = INT_MAX;
28
    int n = grid.size();
29

30
    vector<vector<int>> dp(n, vector<int>(n, -1));
31

32
    for (int j = 0; j < n; j++) {
33
      mini = min(mini, f(n - 1, j, grid, dp));
34
    }
35

36
    return mini;
37
  }
38
};