dynamic programming question (2)

Please find attached.

For each of the dynamic programming problems below, you must:
• Define the table you are using, and define each entry
⚫ Describe how to initialize your table
• Describe the relationship between the entries in your table
• Describe which entry in the table stores your final result
• Provide the pseudocode that shows how to fill up your table
Justify the runtime of your algorithm(b) (8 points)
Recall the e-bike problem from class:
You start your bike ride at mile 0 and must bike exactly n miles. There are battery pick-up stations at
every mile marker, where you can trade your battery for a new fully-charged battery. Each unit of battery
charge allows you to bike one mile. You cannot ride with an empty battery. You can change the battery
before it is empty if you like. As in class, the battery sizes at each station vary. The battery sizes are
contained in the input b[0, …….n] where b[i] is the size of the battery at station i.
New condition:
Now there is an associated cost to exchange the battery at each station.
The costs are stored in the input c[0,…,n] where c[i] is the cost of the battery at station i.
The goal is to find the minimum cost of completing this bike ride.
Your job:
Provide a dynamic programming solution that determines the minimum cost of your trip.
Provide the pseudo-code that prints out the list of stations where you picked up batteries.