Editing 2015 Dec Gold Problem 2 Fruit Feast (section)

== Solution ==

We use dynamic programming to solve this problem. Let dp[i][j] be the maximum tastiness that Bessie can achieve after consuming fruits with a total tastiness of i and taking j naps (0 if no nap is taken, 1 if a nap is taken). We have:

dp[i][0] = max(dp[i-A][0], dp[i-B][0]) if i-A >= 0 or i-B >= 0
dp[i][1] = max(dp[i][1], dp[i//2][0] if i//2 >= 0)

The first equation represents consuming an apple or an orange without taking a nap, while the second equation represents taking a nap after consuming some fruits.

Finally, the maximum tastiness that Bessie can achieve is max(dp[i][1] for i in range(T+1)).

Note that to save memory, we can use a rolling array and compute dp[i] in non-decreasing order of i. The time complexity is O(T), and the space complexity is O(T) without optimizations, or O(1) with a rolling array.