DYNAMIC PROGRAMMING OPTIMIZATION 2 Bob keeps track of the number of times he uses a Metrocard each day for several days. Because there are many rates possible, he seeks to find the minimum cost he could have paid. Consider the cheapest fare functions: they accept a tuple of integers rides that represents the number of rides taken each day and returns the minimum fare to be paid if single rides cost $2.75, seven-day unlimited rides cost $33, and 30-day unlimited rides cost $127. For example, cheapest_fare((2, 0, 1, 9, 10, 10, 10, 10, 10)) represents 2 rides taken on the oth day, 0 rides taken on the ist day, 1 ride taken on the 2nd day, etc. It returns $38.50, where the first day is paid with single rides, no payment is necessary for the second day, and the remaining seven days are paid for with a seven-day unlimited. Provided below is the top-down implementation of the algorithm that finds the cheapest cost of paying for a set of rides. There is also starter code for the bottom-up approach. Complete the second function. rideso (2, 0, 1, 9, 10, 10, 10, 10, 10) # 38.50 (1, 5, 8, 2, 4, 10, 5, 5) # 35.75 rides2 (3, 0, 0, 0, 0, 0, 76, 2) # 38.5 (1, 2, 1, 1, 1, 2, 1, 1) = rides1 rides 3 # 27.5 def cheapest_fare_td (rides, cache={tuple():0}): if rides not in cache: cost1 = rides [-1] * 2.75 cost2 = 33 cost3 = 127 if len(rides) > 1: cost1 += cheapest_fare_td (rides[:-1]) if len(rides) > 7: cost2 += cheapest_fare_td (rides[:-7]) if len(rides) > 30: cost3 += cheapest_fare_td(rides[:-30]) cache (rides] = min(costi, cost2, cost3) return cache [rides] def cheapest_fare_bu (rides): if len(rides) == 0: return 0 cheapest = [0] *len (rides) for idx in range (len (rides)): # fill in code here cheapest [idx] = min(cost1, cost2, cost3) return cheapest [len(rides)-1]