class Solution {
public:
int maxProfit(vector<int> &p)
{
int ret=0;
for(int i=1;i<p.size();++i)
{
if(p[i]>p[i-1])
ret+=p[i]-p[i-1];
}
return ret;
}
int maxProfit(int k, vector<int>& prices) {
if(k>prices.size()/2)return maxProfit(prices);
vector<int> local(k+1,0),global(k+1,0);
for(int i=1;i<prices.size();++i)
{
int diff=prices[i]-prices[i-1];
for(int j=k;j>=1;--j)
{
local[j]=max(global[j-1]+max(diff,0),local[j]+diff);
global[j]=max(global[j],local[j]);
}
for(int j=0;j<=k;++j)
printf("i %d local %d global %d
",i,local[j],global[j]);
}
return global[k];
}
};
一共有n天的股价, 要收益最大,并且交易次数最多k次,
- 这里注意一个问题, n天股价, 最多做n/2 次交易, 因为买卖一次需要两天的股价,n是基数的时候, 是n/2-1次交易, 所以如果k超过n/2直接变成另一个问题了, n天股价怎么获利最大,不限交易次数
- local 和global两个变量的具体含义, 看很多人的说法不同, 初学者颇难理解, local就是dp的核心变量, 计算第i天, 做了j次交易的利润, 然后global相当于最终结果, 按照一般的int ret =0 这样理解, 把local的值和之前的global比较, 取较大值
- local的来源, 第i天做j次交易 = 做j-1次交易加上今天卖出 (i-1天买入, i天卖出,所以代码里面是max(diff,0) ) or 把第j次交易换到今天卖出(原本第j次交易可能是昨天或者之前某天卖出的)
-
for(int j=k;j>=1;--j)这里可以稍微优化下, 因为i是从1慢慢往上加, 所以如果k很大, 第一次走这个循环完全是空跑的,初始化语句可改为 j= min(k,i)
- 第二层for循环 j=k; j>=1; --j , 为什么是反过来循环? 开始想了半天没懂; 采用两种思路理解, 第一种思路如果采用正向循环会怎么样? i=1时, 正向循环反向循环都没区别; =2时,如果正向循环,你会发现local的值计算出来变多了, 这里就是原因! 每次循环到一个新的i值时, 必须把当做第j次交易来假设, 进行计算, 如果是正向循环, 相当于每次交易都会把i 多算一遍!; 第二种思路, 如果采用反向循环的代码如何理解? 每次都从最大值K来计算, k依赖k-1, k-1又依赖k-2, 然后会发现,i=1时, 所有的k都为0, 好像有点奇怪是不是; 因此这里用到了第四点, 如果采用了优化策略循环, 就能好理解点, 其实从 min(i,k)来作为初始值才对, 每次的k依赖的k-1 其实是在上一轮循环计算好的,