leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1463.cpp (920B)

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