2218. 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.

class Solution {
    int dp[1001][2001];
    int helper(vector<vector<int>>& p, int k, int c) {
        if(c == p.size()) return 0;
        if(dp[c][k] != -1) return dp[c][k];
        dp[c][k] = helper(p,k,c+1);
        for(int i = 0; i < p[c].size() and i + 1 <= k; i++) {
            dp[c][k] = max(dp[c][k], helper(p,k-i-1,c+1) + p[c][i]);
        }
        return dp[c][k];
    }
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        int n = piles.size();
        for(int i = 0; i < n; i++) {
            int base = 0;
            for(int j = 0; j < piles[i].size(); j++) {
                base = piles[i][j] += base;
            }
        }
        memset(dp,-1,sizeof(dp));
        
        return helper(piles,k,0);
    }
};