leetcode

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];