Skip to content

Instantly share code, notes, and snippets.

Avatar

Qiankun Zhuang zhuang1992

View GitHub Profile
View Best Time to Buy and Sell Stock IV: at most K transactions.java
// http://blog.csdn.net/fightforyourdream/article/details/14503469
/*
下面的解法主要是能把两次的限制推广到k次交易:
这道题是Best Time to Buy and Sell Stock的扩展,现在我们最多可以进行两次交易。
我们仍然使用动态规划来完成,事实上可以解决非常通用的情况,也就是最多进行k次交易的情况。
这里我们先解释最多可以进行k次交易的算法,然后最多进行两次我们只需要把k取成2即可。
我们还是使用“局部最优和全局最优解法”。
我们维护两种量,一个是当前到达第i天可以最多进行j次交易,最好的利润是多少(global[i][j]),
另一个是当前到达第i天,最多可进行j次交易,并且最后一次交易在当天卖出的最好的利润是多少(local[i][j])。