We have a set of coins in a row, all with positive values. We need to pick a subset of the coins to maximize their sum, with a constraint that we can not pick 3 consecutive coins together.
Example:
[3, 1, ,2 , 3, 10]
ans = 17
Recursion
int maxCoins(vector<int>& coins, int start, int end)
{
if (start > end)
return 0;
if (start == end)
return coins[start];
int skip = maxCoins(coins, start +1, end);
int pickskip = coins[start] + maxCoins(coins, start + 2, end);
int pickpick = coins[start] + coins[start+1] + maxcoins(coins, start + 3, end);
return max(max(skip, pickskip), pickpick);
}TC: O(3^n)
Top Down
int memo[ n + 1] [ n +1] = {-1};
int maxCoins(vector<int>& coins, int start, int end)
{
if (start > end)
return 0;
if (start == end)
return coins[start];
if (memo[start][end] != -1)
return memo[start][end];
int skip = maxCoins(coins, start +1, end);
int pickskip = coins[start] + maxCoins(coins, start + 2, end);
int pickpick = coins[start] + coins[start+1] + maxcoins(coins, start + 3, end);
return memo[start][end] = max(max(skip, pickskip), pickpick);
}
int maxCoins(vector<int>& coins)
{
return maxCoins(coins, 0, coins.size() - 1);
}
Follow-up
a) How will you generalize the above algorithm for:
We have a set of coins in a row, all with positive values. We need to pick a subset of the coins to maximize their sum, with a constraint that we can not pick K consecutive coins together.
b) If you pick a coin, you can pick the next coin. But if you pick two coins, then you have to skip two coins.
What changes are needed in the recursive algorithms
[14, 3, 27, 4, 5, 15, 1]
ans = 61c) How will you generalize part(b) such that you if you pick 'm' coins, then you need to skip 'n' coins before picking up next?