aboutsummaryrefslogtreecommitdiff
path: root/cherry_pickup2.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /cherry_pickup2.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'cherry_pickup2.c')
-rw-r--r--cherry_pickup2.c40
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
+}