diff options
Diffstat (limited to 'other/max_val_k_coin_pile.cpp')
-rw-r--r-- | other/max_val_k_coin_pile.cpp | 42 |
1 files changed, 0 insertions, 42 deletions
diff --git a/other/max_val_k_coin_pile.cpp b/other/max_val_k_coin_pile.cpp deleted file mode 100644 index 6452a7b..0000000 --- a/other/max_val_k_coin_pile.cpp +++ /dev/null @@ -1,42 +0,0 @@ -// 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 -} |