leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1463.cpp (920B)

      1 class Solution {
      2     static int dp[70][70][70];
      3 
      4     static int dfs(const vector<vector<int>> &grid, int r, int c1, int c2) {
      5         const int n = size(grid), m = size(grid[0]);
      6 
      7         if (r == n) return 0;
      8         if (dp[r][c1][c2] != -1) return dp[r][c1][c2];
      9 
     10         int res = 0;
     11         for (int i = -1; i <= 1; i++) {
     12             for (int j = -1; j <= 1; j++) {
     13                 const int nc1 = c1 + i, nc2 = c2 + j;
     14                 if (nc1 < 0 || nc1 >= m || nc2 < 0 || nc2 >= m) continue;
     15                 res = max(res, dfs(grid, r + 1, nc1, nc2));
     16             }
     17         }
     18 
     19         const int cherries = c1 == c2 ? grid[r][c1] : grid[r][c1] + grid[r][c2];
     20         return dp[r][c1][c2] = res + cherries;
     21     }
     22 
     23   public:
     24     int cherryPickup(const vector<vector<int>> &grid) const {
     25         memset(dp, 0xFF, sizeof(dp));
     26         return dfs(grid, 0, 0, size(grid[0]) - 1);
     27     }
     28 };
     29 
     30 int Solution::dp[70][70][70];