先用
f
i
,
j
f_{i,j}
fi,j 表示第
i
i
i 次交易，这次交易到
j
j
j 的最大利润。
这样
f
i
f_i
fi 就可以从
f
i
−
1
f_{i-1}
fi−1 那里直接得到，（参见leetcode123. 买卖股票的最佳时机 III–zhengjun
还要注意一下空间，要滚动
代码
class Solution {
public:
int n
,f
[2][10001];
int maxProfit(int k
,vector
<int>& a
) {
int now
=1,last
=0;
n
=a
.size();
if(k
>n
/2)k
=n
/2;
int ans
=0;
for(int i
=1;i
<=k
;i
++){
memset(f
[now
],0,sizeof(f
[now
]));
int maxx
=-0x3fffffff;
for(int j
=0;j
<n
;j
++){
f
[now
][j
]=max(maxx
+a
[j
],j
?f
[now
][j
-1]:0);
if(maxx
<f
[last
][j
]-a
[j
])maxx
=f
[last
][j
]-a
[j
];
}
if(ans
<f
[now
][n
-1])ans
=f
[now
][n
-1];
now
^=1;last
^=1;
}
return ans
;
}
};
