java卡车送货经过n个城镇买货或者卖货求最大利润

Question

从起点城镇到目的地城镇的送货卡车，在途中经过多个城镇。在沿途的每一个城镇都有选择，卡车要么买新的负载，要么卖出其现有的负载在价值，而已每个城镇的买的价格必定大于卖的价格，卡车一次只能运输一个负载，最多只能停止 2k ≤ n 次来接载或卸货。
开发算法：可以指示卡车司机，在哪个城镇最好装货或卸货，以便卡车获得最好的整体利润。
该任务应包括以下组件：

1. 暴力方法 ，就是把所有可能的情况求出来再计算最大值。
2. 精确方法，演示正确和高效地解决送货卡车问题的方法。

暴力算法思路简单，但是在排列组合的地方就卡住了，不知道该怎么实现，求解答。

Answer 1

只能给你说思路，写不了代码，除非像leetcode那样有跑不过的用例提示。不然写不出来。

用数组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：算法题中，算是困难类型的了。。。