Question

Lara owns a flower shop, where she sells only two types of flower bouquets Type 1: The first type of bouquet contains three roses and costs p dollars. Type 2: The second type of bouquet contains one cosmos and one rose and costs q dollars Lara grows these flowers in her own garden in a single row. Consider the row as a one-dimensional array where each cell either contains a rose or a cosmos. For example array 001101011 here 0 indicates rose and 1 indicates cosmos. Lara follows an important rule when she makes the bouquets: she makes each bouquet with only consecutive flowers from the array. For example, in a bouquet, the flower from consecutive indices (i, i+1, and i+2) in the array can be present, but not from non-consecutive indices (i and i+2). In the array above, Lara cannot make any bouquets of type 1 but she can make 3 bouquets of type 2 Now she wonders what is the maximum profit she can make if she makes these bouquets optimally. You are given a binary string representing her garden row. Calculate the maximum profit Lara can make. Remember that it is not necessary to use every flower. Function Description Complete the flowerBouquets function in the editor below. The function must return an integer that denotes the maximum profit Lara can make if she makes her bouquets optimally flowerBouquets has three parameters: p: integer denoting the cost of a bouquet of type 1 q: integer denoting the cost of a bouquet of type 2 s: string denoting the garden pattern, where zero indicates rose and one indicates cosmos Constraints 1 sp, q s1000

Answer 1

This involves the use of dynamic programming

Dynamic Programming:

It is a technique in which we use an array to dynamically store and update the desired result. It is an optimization over recursion. Instead of re solving the smaller cases again and again we evaluate the result only once for each value and store the result.

Approach:

If you haven't heard about dynamic programming before you must look it up over google or ask me in the comments.

In this question we will use an array of same size as the size of the input string as our DP array.

DP[i] stores the maximum profit we could obtain had we been given only the string from index i to the end.

Hence DP[0] will denote the maximum profit we can get if we are given entire string

Three cases arise at each index

1. We do not use this flower at all in our bouquets. In this case simply, dp[i] = dp[i + 1]

2. We use next three flowers to make a bouquet of first type(if we can). In this case dp[i] = p + dp[i + 3]

3. We use next three flowers to make a bouquet of second type(if we can). In this case dp[i] = q + dp[i + 2]

Note:

The code itself has comments attached .

If you find it hard to understand any part hit me up in the comments.

CODE:

SAMPLE OUTPUT:

RAW CODE:

#include

using namespace std;

bool canMakeRose(int beg, string s){

int n = s.size();

if(beg + 2 >= n) return false;

return (s[beg] == '0' && s[beg + 1] == '0' && s[beg + 2] == '0');

}

bool canMakeCosmos(int beg, string s){

int n = s.size();

if(beg + 1 >= n) return false;

if(s[beg] == '0' && s[beg + 1] == '1') return true;

if(s[beg] == '1' && s[beg + 1] == '0') return true;

return false;

}

int flowerBouquets(string s, int p, int q){

int dp[100000];

int n = s.size();

for(int i = n - 1; i >= 0; i--){

dp[i] = 0;

if(canMakeRose(i, s)){

int profit = p;

if(i + 3 < n){

profit = profit + dp[i + 3];

}

dp[i] = max(dp[i], profit);

}

if(canMakeCosmos(i, s)){

int profit = q;

if(i + 2 < n){

profit = profit + dp[i + 2];

}

dp[i] = max(dp[i], profit);

}

if(i + 1 < n) dp[i] = max(dp[i], dp[i + 1]);

}

return dp[0];

}

int main(){

string s;

int p, q;

cin >> s;

cin >> p >> q;

cout << "Max Profit : " << flowerBouquets(s, p, q) << endl;

}