We have multiple options within the given budget. Trying all of them will take exponential time. How can we improve that?

We can use dynamic programming to speed up the algorithm.

We have three options for each fruit. To skip it, to buy it with a coupon, or to buy it without a coupon.