leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

cherry_pickup2.c (1377B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 1463. Cherry Pickup II
#include "leetcode.h"

/*
 * given a row * cols matrix grid representing a field of cherries where
 * 'grid[i][j]' represents the number of cherries that you can collect from the
 * '(i, j)' cell. you have two robots that can collect cherries for you located
 * at corner (0, 0) and (cols - 1). return the maximum number of cherries
 * collection using both robots by following the rulew below.
 */

int dp[70][70][70];

int dfs(int **grid, int size, int col_size, int i, int l, int r) {
  if (i >= size || l == r)
    return 0;
  if (l < 0 || l >= col_size || r < 0 || r >= col_size)
    return 0;
  if (dp[i][l][r] >= 0)
    return dp[i][l][r];
  int res = 0, dir[3] = {-1, 0, 1};
  for (int x = 0; x < 3; x++)
    for (int y = 0; y < 3; y++) {
      int tmp = dfs(grid, size, col_size, i + 1, l + dir[x], r + dir[y]);
      res = res > grid[i][l] + grid[i][r] + tmp ? res
                                                : grid[i][l] + grid[i][r] + tmp;
    }
  return dp[i][l][r] = res;
}

int cherryPickup(int **grid, int grid_size, int *grid_col_size) {
  memset(dp, -1, sizeof(dp));
  return dfs(grid, grid_size, *grid_col_size, 0, 0, *grid_col_size - 1);
}

int main() {
  int grid[4][3] = {{3, 1, 1}, {2, 5, 1}, {1, 5, 5}, {2, 1, 1}};
  int grid_col_size[] = {};
  printf("%d\n", cherryPickup((int **)grid, 4, grid_col_size)); // expect: 24
}