leetcode

commit 8997dd6fa24201a2f502273325f43d6888492b69
parent dc4b4db87436e611f1a3466b93d61b0e7c57dfb9
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 15 Apr 2023 14:14:44 +0200

Daily Problem

Diffstat:
A
Problems/2218.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 19 insertions(+), 0 deletions(-)
diff --git a/Problems/2218.cpp b/Problems/2218.cpp
@@ -0,0 +1,18 @@
+class Solution {
+  int dp[1001][2001] = {0};
+
+public:
+  int maxValueOfCoins(const vector<vector<int>> &piles, int left,
+                      int pile = 0) {
+    if (!left || pile >= piles.size()) return 0;
+    if (dp[pile][left]) return dp[pile][left];
+
+    int res = maxValueOfCoins(piles, left, pile + 1), sum = 0;
+    for (int i = 0; i < piles[pile].size() && i < left; i++) {
+      res = max(res, (sum += piles[pile][i]) +
+                         maxValueOfCoins(piles, left - i - 1, pile + 1));
+    }
+
+    return dp[pile][left] = res;
+  }
+};
diff --git a/README.md b/README.md
@@ -481,6 +481,7 @@ for solving problems.
 |  2181  |   Medium   | [Merge Nodes in Between Zeros](Problems/2181.cpp)                                                |
 |  2187  |   Medium   | [Minimum Time to Complete Trips](Problems/2187.cpp)                                              |
 |  2192  |   Medium   | [All Ancestors of a Node in a Directed Acyclic Graph](Problems/2192.cpp)                         |
+|  2218  |    Hard    | [Maximum Value of K Coins From Piles](Problems/2218.cpp)                                         |
 |  2235  |    Easy    | [Add Two Integers](Problems/2235.cpp)                                                            |
 |  2236  |    Easy    | [Root Equals Sum of Children](Problems/2236.cpp)                                                 |
 |  2243  |    Easy    | [Calculate Digit Sum of a String](Problems/2243.cpp)                                                 |