思路
1.我们使用buy[i][j]来表示第i天已经进行了j次交易，而且现在持有着一只股票的最大收益，sell[i][j]表示第i天进行了j次交易，而且现在不持有股票的最大收益。
2.容易求解状态迁移方程
{
b
u
y
[
i
]
[
j
]
=
m
a
x
b
u
y
[
i
?
1
]
[
j
]
,
s
e
l
l
[
i
?
1
]
[
j
?
1
]
?
p
r
i
c
e
s
[
i
]
s
e
l
l
[
i
]
[
j
]
=
m
a
x
s
e
l
l
[
i
?
1
]
[
j
]
,
b
u
y
[
i
?
1
]
[
j
]
+
p
r
i
c
e
s
[
i
]
\begin{cases} buy[i][j] = max { buy[i-1][j] , sell[i-1][j-1] - prices[i] } \\ sell[i][j] = max { sell[i-1][j] , buy[i-1][j] + prices[i] }\\ \end{cases}
{buy[i][j]=maxbuy[i?1][j],sell[i?1][j?1]?prices[i]sell[i][j]=maxsell[i?1][j],buy[i?1][j]+prices[i]?
3.初始化
buy[0][1…k] = - prices[0]，之所以k可以取2…k的值，是因为我们将多出来的交易次数都看作是收益为0的操作，由此可得 sell[0][0…k] = 0，因此我们最后结果是取sell[n-1][k]的值，尽管其并没有操作这么多次，但是我们在开始时将多次收益为0的操作填补其空缺的次数。
4.k的取值讨论，因为一买一卖的缘故，所以k绝不可能大于
?
n
/
2
?
\lceil n/2 \rceil
?n/2?。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size()==0)
return 0;
int n=prices.size();
k=min(k,n/2);
vector<int> buy(k+1);
vector<int> sell(k+1);
sell[0]=0;
for(int i=1;i<=k;i++)
{
buy[i]=0-prices[0];
sell[i]=0;
}
for(int i=1;i<n;i++)
{
for(int j=k;j>=1;j--)
{
int t=buy[j];
buy[j]=max(sell[j-1]-prices[i],buy[j]);
sell[j]=max(sell[j],t+prices[i]);
}
buy[0]=max(buy[0],0-prices[i]);
}
return sell[k];
}
};
|