LeetCode 188. Best Time to Buy and Sell Stock IV
Description
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
描述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
思路
- 这道题使用动态规划.
- 我们用一个二维矩阵trans，矩阵的列表示交易的价格，矩阵的行表示交易的次数，矩阵的值表示当前能够获得的最大利润.如上图所示，第一行表示进行0次交易，获得的利润为0；第一列表示在第一天（索引为0）进行交易，只有一天无法进行完整的交易，所以活力为0.
- 以允许3次交易，第3天为例，trans[3][3],我们有如下的选择：
- 1，在这一天我们什么什么都不做，于是我们获得昨天tans[3][2]的利润
- 2.我们以今天的价格为卖出价，以第0天为买进价，则可以获得利润pri1 = pries[3]-prices[0](占用一次交易次数)+trans[2][0](截止第0天，交易2次获得最大利润)
- 3.我们以今天的价格为卖出价，以第1天为买进价，则可以获得利润pri2 = pries[3]-prices[1](占用一次交易次数)+trans[2][1](截止第1天，交易2次获得最大利润)
- 4.我们以今天的价格为卖出价，以第2天为买进价，则可以获得利润pri3 = pries[3]-prices[2](占用一次交易次数)+trans[2][2](截止第2天，交易2次获得最大利润)
- 于是tans[3][3] = max(tans[3][2],pri1,pri2,pri3)
- 同理tans[3][4]的最大值：
- 1，在这一天我们什么什么都不做，于是我们获得昨天tans[3][3]的利润
- 2.我们以今天的价格为卖出价，以第0天为买进价，则可以获得利润pri1 = pries[4]-prices[0](占用一次交易次数)+trans[2][0](截止第0天，交易2次获得最大利润)
- 3.我们以今天的价格为卖出价，以第1天为买进价，则可以获得利润pri2 = pries[4]-prices[1](占用一次交易次数)+trans[2][1](截止第1天，交易2次获得最大利润)
- 4.我们以今天的价格为卖出价，以第2天为买进价，则可以获得利润pri3 = pries[4]-prices[2](占用一次交易次数)+trans[2][2](截止第2天，交易2次获得最大利润)
- 5.我们以今天的价格为卖出价，以第2天为买进价，则可以获得利润pri4 = pries[4]-prices[3](占用一次交易次数)+trans[2][3](截止第3天，交易2次获得最大利润)
- 这样我们就可以求得第k次交易的最大值.
- 我们将-prices[0](占用一次交易次数)+trans[2][0]记为P1，-prices[1](占用一次交易次数)+trans[2][1]记为P2，-prices[2](占用一次交易次数)+trans[2][2]记为P3
- 时间复杂度O(n^3)，我们发现观察上面的过程可以发现，在判断tans[3][3]的值的时候，其中P1，P2，P3，已经被计算过，而我们要求的值
- tans[3][4]= max(tans[3][3],pries[4]+P1,pries[4]+P2,pries[4]+P3,pries[4]-prices[3](占用一次交易次数)+trans[2][3]).
- tans[3][4]= max(tans[3][3],pries[4]+max(P1,P2,P3,-prices[3](占用一次交易次数)+trans[2][3])).
- 于是我们可以首先计算max(P1,P2,P3,-prices[3](占用一次交易次数)+trans[2][3])=maxdiff，这样就可以减少一次循环.
- 空间复杂度O(n^2),通过上面的描述发现，每次在被允许k次交易的时候，我们只需要知道第k-1次交易的信息，k-2，k-3已经不需要知道了，所以我们只用生成一个两行的矩阵即可.
- 还需要注意的是，n天最多可以进行n/2取整次交易，当给定的交易次数k>=n/2时,题目相当于转换成了可以被允许进行无限次交易.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-01-19 12:53:32
# @Last Modified by: 何睿
# @Last Modified time: 2019-01-19 14:31:38
class Solution:
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
#交易次数为0或者交易天数小于2时无法进行交易，返回0
if len(prices) < 2 or k == 0:
return 0
# n天最多可以交易n//2次，当允许的交易次数大于这个天数的时候，这道题就转换
# 成了不限制交易次数
if k >= (len(prices) // 2):
return sum(i - j for i, j in zip(prices[1:], prices[:-1]) if i - j > 0)
# 生命矩阵，动态规划
# 为了避免出现内存超出限制，根据本题的特点，矩阵只需要两行就够了
row, col = 2, len(prices)
trans = [[0 for _ in range(col)] for _ in range(row)]
# 进行k次交易
for i in range(k):
maxdiff = trans[i % 2][0] - prices[0]
for j in range(1, col):
maxdiff = max(maxdiff, trans[i % 2][j - 1] - prices[j - 1])
trans[(i + 1) % 2][j] = max(trans[(i + 1) % 2][j - 1],maxdiff + prices[j])
return max(trans[0][col - 1], trans[1][col - 1])
