This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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])。 |