diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /cherry_pickup2.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'cherry_pickup2.c')
-rw-r--r-- | cherry_pickup2.c | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/cherry_pickup2.c b/cherry_pickup2.c new file mode 100644 index 0000000..77a9d09 --- /dev/null +++ b/cherry_pickup2.c @@ -0,0 +1,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 +} |