College students get a lot of free food at various events. suppose you have a schedule of the next n days marked with those days when you get a free dinner, and those days on which you must acquire dinner on your own. on any given day you can buy dinner at the cafeteria for $6. alternatively, you can purchase one week’s groceries for $20, which will provide dinner for each day that week. however, because you don’t have a fridge, the groceries will go bad after seven days (including the day of purchase) and any leftovers must be discarded. due to your very busy schedule, these are your only three options for dinner each night.
write a dynamic programming algorithm to determine, given the schedule of free meals, the minimum amount of money you must spend to make sure you have dinner each night and to print the dates on which you should purchase groceries. explain why your algorithm is correct and has running time polynomial in n, the number of days on the schedule.
hint: start by writing a recursive procedure to determine how you should eat dinner on the last night.
language: c++