三维DP,本质和股票123没区别;

第i天交易次数0不持有股票的情况只能来自第i-1天交易次数0不持有股票
第i天交易j次不持有股票的状态可以来自第i-1天交易j次不持有股票或者第i-1天交易j-1次持有股票
第i天交易j次持有股票的状态可以来自第i-1天交易j次持有股票或者第i-1天交易j次不持有股票

#include<bits/stdc++.h>
using namespace std;

int m_maxProfit(vector<int>& prices, int pricesSize){
    int hode = INT_MIN,cash = 0,i = 0,bh_hode = INT_MIN;
    for(i = 0;i < pricesSize;i++){
        hode = max(hode,cash - prices[i]);
        cash = max(bh_hode + prices[i],cash);
        bh_hode = hode;
    }
    return cash;
}


int maxProfit(int k, vector<int>& prices) {
    int i = 0,j = 0,n = prices.size();
    if(n < 2)return 0;
    if(k >= n/2) return m_maxProfit(prices,n);//超过了就是没限制
    vector<vector<int>> cash(n, vector<int>(k + 1,0));
    vector<vector<int>> hode(n, vector<int>(k + 1,INT_MIN));
    for(j = k;j > 0;j--){
        cash[i][j] = max(hode[0][j] + prices[i],cash[0][j]);
        hode[i][j] = max(hode[0][j],cash[i][j - 1] - prices[i]);
    }
    for(i = 1;i < n;i++){
        for(j = k;j > 0;j--){
           cash[i][j] = max(hode[i-1][j] + prices[i],cash[i - 1][j]);
           hode[i][j] = max(hode[i-1][j],cash[i - 1][j - 1] - prices[i]);
        }
    }
    return cash[n - 1][k];
}

int main(){
    int n,k,p;
    cin >> n >> k;
    vector<int>arr(n);
    for(int i = 0;i < n;i ++){
        cin >> p;
        arr[i] = p;
    }
    cout << maxProfit(k,arr);
    return 0;
}