You're playtesting a new boardgame from one of your friends in the Game Design major, and they want your help to figure out the optimal strategy. The game has n rounds and in each round 1 = i = n you must acquire si tokens. There are two possible ways to acquire tokens in round i:
A) Spend r dollars per token, so r · si in total, to acquire all token of round i.
B) Spend C dollars to acquire the tokens of round i and of the next 3 rounds, independently of how many there are. (If you do this in round i, then your next choices concern rounds i + 4 and greater).
Example. Suppose r = 1, C = 40, and the sequence of si is 11, 9, 9, 12, 12, 12, 12, 9, 9, 11. Then the cheapest way to acquire all the tokens is to choose action A for the first three rounds, then action B once, and then action A for the final three rounds.
Give a dynamic programming algorithm for finding the cheapest way to acquire all tokens, given the sequence s1, s2, . . . , sn. You must describe not only how you determine the value of the optimal sequence of actions, but also the sequence of actions itself.
Solve using Dynamic Programming:
1) Write the identity for the OPT value.
2) Explain why the identity holds.
3) Describe data structure you will use to store OPT value for the subproblems and the order in which you will fill out the entries in your data structure.
4) In the problems you are asked to return the solution ( not just the value of the solution), state the additional information you record which will allow you to retrace your steps and report an optimal solution.
5) Bound the running time by the size of the data structure and the work per entry in it.