leetcode

commit 51904d519bbf95ed965c3c6052e9a94eda24db6b
parent 31e031c600c89fe462f2455d086bcdcbd8642b75
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 11 Feb 2024 15:35:03 +0000

Daily Problem

Diffstat:
A
Problems/1463.cpp
 | 
30
++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 31 insertions(+), 0 deletions(-)
diff --git a/Problems/1463.cpp b/Problems/1463.cpp
@@ -0,0 +1,30 @@
+class Solution {
+    static int dp[70][70][70];
+
+    static int dfs(const vector<vector<int>> &grid, int r, int c1, int c2) {
+        const int n = size(grid), m = size(grid[0]);
+
+        if (r == n) return 0;
+        if (dp[r][c1][c2] != -1) return dp[r][c1][c2];
+
+        int res = 0;
+        for (int i = -1; i <= 1; i++) {
+            for (int j = -1; j <= 1; j++) {
+                const int nc1 = c1 + i, nc2 = c2 + j;
+                if (nc1 < 0 || nc1 >= m || nc2 < 0 || nc2 >= m) continue;
+                res = max(res, dfs(grid, r + 1, nc1, nc2));
+            }
+        }
+
+        const int cherries = c1 == c2 ? grid[r][c1] : grid[r][c1] + grid[r][c2];
+        return dp[r][c1][c2] = res + cherries;
+    }
+
+  public:
+    int cherryPickup(const vector<vector<int>> &grid) const {
+        memset(dp, 0xFF, sizeof(dp));
+        return dfs(grid, 0, 0, size(grid[0]) - 1);
+    }
+};
+
+int Solution::dp[70][70][70];
diff --git a/README.md b/README.md
@@ -769,6 +769,7 @@ for solving problems.
 |  1458  |    Hard    | [Max Dot Product of Two Subsequences](Problems/1458.cpp)                                           |
 |  1461  |   Medium   | [Check If a String Contains All Binary Codes of Size K](Problems/1461.cpp)                         |
 |  1462  |   Medium   | [Course Schedule IV](Problems/1462.cpp)                                                            |
+|  1463  |    Hard    | [Cherry Pickup II](Problems/1463.cpp)                                                              |
 |  1464  |    Easy    | [Maximum Product of Two Elements in an Array](Problems/1464.cpp)                                   |
 |  1466  |   Medium   | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp)                        |
 |  1470  |    Easy    | [Shuffle the Array](Problems/1470.cpp)                                                             |