Consider the following inventory problem. You are running a company that sells some large product (say trucks), and predictions tell you the quantity of sales to expect over the next n months. Let di denote the number of sales you expect in month i. Well assume that all sales happen at the beginning of the month, and trucks that are not sold are stored until the beginning of the next month. You can store at most S trucks, and it costs C to store a single truck for a month. You receive shipments of trucks by placing orders for them, and there is a fixed ordering fee of K each time you place an order (regardless of the number of trucks you order). You start out with no trucks. The problem is to design an algorithm that decides how to place orders so that you satisfy all the demands {di}, and minimize the costs.

To summarize:

Your algorithm receives as input the demands {di}, the costs C and K, and the inventory limit S.

Your algorithm should output how many trucks to order in each of the n months; you may skip ordering in some of the months.

In each month you need enough trucks to satisfy the demand di but the number left over after satisfying the demand for the month should not exceed the limit S.

Your total cost is K times the number of orders placed plus the sum over the months of C times the number of trucks left over after sales that month.

Give a DP-based algorithm that solves this problem in time polynomial in n. (Solutions with a running time that depends on parameters other than n will receive partial credit.) Give a brief argument for the correctness of your recursive equation as well as a brief argument bounding the running time of your algorithm.