只能给你说思路,写不了代码,除非像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:算法题中,算是困难类型的了。。。