aboutsummaryrefslogtreecommitdiff
path: root/other/max_val_k_coin_pile.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/max_val_k_coin_pile.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/max_val_k_coin_pile.cpp')
-rw-r--r--other/max_val_k_coin_pile.cpp42
1 files changed, 42 insertions, 0 deletions
diff --git a/other/max_val_k_coin_pile.cpp b/other/max_val_k_coin_pile.cpp
new file mode 100644
index 0000000..6452a7b
--- /dev/null
+++ b/other/max_val_k_coin_pile.cpp
@@ -0,0 +1,42 @@
+// 2218. Maximum Value of K Coins From Piles
+#include "leetcode.h"
+
+/*
+ * there are 'n' piles of coins on a table. each pile consists of a positive
+ * number of coins of assorted denominations. in one move you can choose any
+ * coin on top of a pile remove it and add it to your wallet. given a list of
+ * 'piles' where 'piles[i]' is a list of integers denoting the composition of
+ * the i'th pile from top to bottom, and a positive integer 'k', return the
+ * maximum total values of coins you can have in your wallet if you choose
+ * exactly 'k' coins optimally.
+ */
+
+class Solution {
+public:
+ int maxValueOfCoins(vvd & piles, int k) {
+ int n = piles.size(), m[1001][2001] = {};
+ memset(m, -1, sizeof(m));
+ function<int(int, int)> dp = [&](int i, int j) {
+ if (m[i][j] != -1)
+ return m[i][j];
+ if (i == n)
+ return 0;
+ int ans = dp(i + 1, j), sum = 0;
+ for (int k = 1; k <= j && k <= piles[i].size(); ++k) {
+ sum += piles[i][k - 1];
+ ans = max(ans, dp(i + 1, j - k) + sum);
+ }
+ return m[i][j] = ans;
+ };
+ return dp(0, k);
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd
+ p1 = {{1, 100, 3}, {7, 8, 9}},
+ p2 = {{100}, {100}, {100}, {100}, {100}, {100}, {1, 1, 1, 1, 1, 1, 700}};
+ printf("%d\n", obj.maxValueOfCoins(p1, 2)); // expect: 101
+ printf("%d\n", obj.maxValueOfCoins(p2, 7)); // expect: 706
+}