Maximum Value of K Coins From Piles LeetCode solution in C++

1
class Solution {
2
 public:
3
  int dp[1001][2001]; // Dp array For Memoization.
4
  int solve(vector<vector<int>> &v, int index, int coin) {
5
    if (index >= v.size() || coin == 0) // Base Condition
6
      return 0;
7
    if (dp[index][coin] != -1) // Check wheather It is Already Calculated Or
8
                               // not.
9
      return dp[index][coin];
10

11
    /* Our 1st choice :- We not take any Coin from that pile*/
12
    int ans = solve(v, index + 1, coin); // Just Call function for next Pile.
13

14
    /*Otherwise we can take Coins from that Pile.*/
15
    int loop = v[index].size() - 1;
16
    int sum = 0;
17

18
    for (int j = 0; j <= min(coin - 1, loop); j++) //
19
    {
20
      sum = sum + v[index][j];
21
      ans = max(ans, sum + solve(v, index + 1, coin - (j + 1)));
22

23
      /*Aove we Pass coin-(j+1). Because till j'th index we have taken j+1 coin
24
       * from that pile.*/
25
    }
26

27
    return dp[index][coin] = ans;
28
  }
29
  int maxValueOfCoins(vector<vector<int>> &piles, int k) {
30
    memset(dp, -1, sizeof(dp));
31
    return solve(piles, 0, k);
32
  }
33
};