Suppose you work at a restaurant as a waiter. One night, only you and a coworker are staffed. At the end of the night, you decide to split the tips. You notice that you have 2k many bills (where k is an integer) of the following denominations: $1, $2, $5, and $10 bills. First, you and your co-worker spread out the bills in a fixed, non-ascending order. You both agree to take turns picking a bill to keep by selecting either the leftmost or the rightmost bill, and you are allowed to have the first pick. Knowing that your co-worker will adopt the strategy of always choosing the larger denomination on his turn, develop a recurrence relation that will maximize the amount of tips you get to keep.
Suppose you work at a restaurant as a waiter. One night, only you and a coworker are staffed. At the end of the night, you decide to split the tips. You notice that you have 2k many bills (where k is an integer) of the following denominations: $1, $2, $5, and $10 bills. First, you and your co-worker spread out the bills in a fixed, non-ascending order. You both agree to take turns picking a bill to keep by selecting either the leftmost or the rightmost bill, and you are allowed to have the first pick. Knowing that your co-worker will adopt the strategy of always choosing the larger denomination on his turn, develop a recurrence relation that will maximize the amount of tips you get to keep.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
