
这道题是买卖股票问题的终极版,即给定一个数组表示各天的股价,给定k表示最多可以交易的次数(一次交易定义为buy+sell),各次交易之间不能交叉,问最大收益是多少。
这题可以使用动态规划求解。记为在
天进行至多
次
次交易可以得到的最大收益。不难写出转移方程:
其意义为,在第天我们有两个选择:
1、什么都不做(或买入)。此时收益与第天相同,为
。
2、卖出股票。若想在第天卖出股票,须在第
天(
)买入股票,最大收益是
。即在
天进行至多
次交易的最大收益加上第
天卖出股票取得的收益。
按照上述过程进行计算,算法复杂度为,并不是非常理想。能否优化计算过程呢?将
写成如下形式:
。
从而我们可以把循环写成如下形式:
DP loop:
for i : 1 -> k
maxTemp = -prices[0];
for j : 1 -> n-1
dp[i][j] = max(dp[i][j-1], prices[j]+maxTemp);
maxTemp = max(maxTemp, dp[i-1][j-1]-prices[j]);
return dp[k][n-1];
从而我们的算法复杂度降到了,完整代码如下:
class Solution
{
public:
int maxProfit(int k, vector<int> &prices)
{
int n=prices.size();
if (n<2) return 0;
if (k>n/2)
{
int ans=0;
for (int i=1;i<n;i++)
ans+=max(prices[i]-prices[i-1],0);
return ans;
}
vector<vector<int>> dp(k+1,vector<int>(n,0));
int maxTemp;
for(int i=1;i<=k;i++)
{
maxTemp=-prices[0];
for(int j=1;j<n;j++)
{
dp[i][j]=max(dp[i][j-1],prices[j]+maxTemp);
maxTemp=max(maxTemp,dp[i-1][j-1]-prices[j]);
}
}
return dp[k][n-1];
}
};

网友评论