Consider a delivery truck that travels from a start town to a destination town
passing by multiple towns en route. At each of the n towns along the route
there is the option for the truck to either pick up a new load at cost ci specific
for town i, or else drop off its existing load at a value vi ≤ ci specific for town
i. The truck can only transport one load at a time and can only stop at most
2k ≤ n times to pick up or drop off a load.
The purpose of this assignment is to develop algorithms that can indicate to
a truck driver at which towns it is best to pick up or drop off in order for the
truck to get the best overall profit.
Exact Approach which is a program that demonstrates an approach that
correctly and efficiently solves the delivery truck problem. Please include
comments in your program that clearly explain the approach you have
taken, particularly why it works, and include good test cases that illustrate
its correctness.
求一个详细点的思路，需要用动态规划，最好思路有详细思考过程
用数组price[0,1,2...n]表示每个城镇的货物价值
题目：低买高卖，限制买卖次数k次。
我们用 buy[i][j] 表示对于数组prices[0..i] 中的价格而言，进行恰好 j次交易，并且车上还有一个货物，这种情况下的最大利润。
用sell[i][j]表示这种情况下，车上没有货物时候的最大利润；用cost表示此时车上货物的价值
推导：
对于buy[i][j] ,如果是第i站进行了交易，如果此时不持有货物那么最大利润就是sell[i-1][j-1] - price[i]
如果此时持有货物，那么最大利润就是buy[i-1][j-1]-price[i]+cost
那么buy[i][j] = Max{sell[i-1][j-1] - price[i]，buy[i-1][j-1]-price[i]+cost }
对于sell[i][j]，此时持有货物，那么最大利润就是持有的卖出 buy[i-1][j-1] + cost
如果此时不持有货物，最大利润就是sell[i-1][j]
那么sell[i][j] = Max{ buy[i-1][j-1] + cost, sell[i-1][j] }
在k次交易后，不持有货物利润最大，所以答案在sell[n-1][0...k]中的最大值。
ps：算法题中，算是困难类型的了。。。