Cherry Pickup II LeetCode solution in C++

1
class Solution {
2
 public:
3
  int cherryPickup(vector<vector<int>> &grid) {
4
    int n = grid.size();
5
    int m = grid[0].size();
6
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(m, 0)));
7

8
    for (int i = 0; i < m; i++) {
9
      for (int j = 0; j < m; j++) {
10
        if (i == j)
11
          dp[n - 1][i][j] = grid[n - 1][i];
12
        else
13
          dp[n - 1][i][j] = grid[n - 1][i] + grid[n - 1][j];
14
      }
15
    }
16
    for (int i = n - 2; i >= 0; i--) {
17
      for (int j1 = 0; j1 < m; j1++) {
18
        for (int j2 = 0; j2 < m; j2++) {
19
          int maxi = -1e8;
20
          for (int dj1 = -1; dj1 <= 1; dj1++) {
21
            for (int dj2 = -1; dj2 <= 1; dj2++) {
22
              int value = 0;
23
              if (j1 == j2)
24
                value = grid[i][j2];
25
              else
26
                value = grid[i][j1] + grid[i][j2];
27

28
              if (j1 + dj1 >= 0 && j1 + dj1 < m && j2 + dj2 >= 0 && j2 + dj2 < m)
29
                value += dp[i + 1][j1 + dj1][j2 + dj2];
30
              else
31
                value += -1e8;
32
              maxi = max(maxi, value);
33
            }
34
          }
35
          dp[i][j1][j2] = maxi;
36
        }
37
      }
38
    }
39
    return dp[0][0][m - 1];
40
  }
41
};