Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 15

Description

Maximum Value of K Coins From Piles

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 any pile, remove it, and add it to your wallet.

Given a list piles, where piles[i] is a list of integers denoting the composition of the ith pile from top to bottom, and a positive integer k, return the maximum total value of coins you can have in your wallet if you choose exactly k coins optimally.

Example 1:

Input: piles = [[1,100,3],[7,8,9]], k = 2
Output: 101
Explanation:
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.

Example 2:

Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
Output: 706
Explanation:
The maximum total can be obtained if we choose all coins from the last pile.

Constraints:

• n == piles.length
• 1 <= n <= 1000
• 1 <= piles[i][j] <= 105
• 1 <= k <= sum(piles[i].length) <= 2000

Solution

bottom-up approach

class Solution {
public:
  int maxValueOfCoins(vector<vector<int>>& piles, int k) {
    int n = piles.size();
    vector<vector<int>> dp(n + 1, vector<int>(k + 1));

    for(int p = 0; p < n; ++p) {
      dp[p + 1] = dp[p];
      int sum = 0;
      for(int i = 0; i < min<int>(piles[p].size(), k); ++i) {
        sum += piles[p][i];
        for(int j = 0; j + i + 1 <= k; ++j) {
          // cout << p + 1 << ' ' << j + i + 1 <<  ' ' << j << endl;
          dp[p + 1][j + i + 1] = max(dp[p + 1][j + i + 1], dp[p][j] + sum);
        }
        // cout << "OUT!?" << endl;
      }
    }

    return dp[n][k];
  }
};

// Accepted
// 122/122 cases passed (391 ms)
// Your runtime beats 29.06 % of cpp submissions
// Your memory usage beats 65.97 % of cpp submissions (18.1 MB)

top-down approach

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  int maxValueOfCoins(vector<vector<int>>& piles, int k) {
    int n = piles.size();
    for(auto &pile : piles) {
      for(int i = 1; i < pile.size(); ++i) {
        pile[i] += pile[i - 1];
      }
    }
    vector<vector<int>> dp(n, vector<int>(k + 1));

    function<int(int, int)> solve = [&](int pile, int rest) {
      if(!rest || pile == n) return 0;
      if(dp[pile][rest]) return dp[pile][rest];
      int result = solve(pile + 1, rest);
      for(int i = 0; i < piles[pile].size() && i < rest; ++i) {
        result = max(result, piles[pile][i] + solve(pile + 1, rest - i - 1));
      }

      return dp[pile][rest] = result;
    };

    return solve(0, k);
  }
};

// Accepted
// 122/122 cases passed (447 ms)
// Your runtime beats 23.03 % of cpp submissions
// Your memory usage beats 46.34 % of cpp submissions (18.4 MB)