c++ 题解 | #买卖股票的最好时机(四)#

和买卖股票的最好时机(三)思路类似： dp[n][k*2]中的dp[i][kk]：
当kk==0、2、4、6...，是第1、2、3、4...次持有状态
当kk==1、3、5、7...，是第1、2、3、4...次不持有状态
初始化：
所有的第一天的 任何次 持有状态的收益值都是 -p[i]，所有的第一天的 任何次 未持有状态的收益值都是 -p[i]

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1010;
int p[N];
int n, k;
int dp[N][210];

int main() {

    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
    }
    //初始化
    for (int j = 0; j < k*2; j++) {
        if (j % 2 == 0)
            dp[1][j] = -p[1];
        else
            dp[1][j] = 0;
    }
    for (int i = 2; i <= n; i++) {
        for (int kk = 0; kk < k*2; kk++) {
            if (kk == 0) {
                dp[i][kk] = max(dp[i - 1][kk], -p[i]);
            } else {
                if (kk % 2 == 0) {
                    dp[i][kk] = max(dp[i - 1][kk], dp[i - 1][kk - 1] - p[i]);
                } else {
                    dp[i][kk] = max(dp[i - 1][kk], dp[i - 1][kk - 1] + p[i]);
                }
            }
        }
    }
    //cout << dp[2][1]<< "--" << dp[4][3] << "--" << dp[6][5] << endl; 
    int ans = 0;
    for(int j=0;j<k*2;j++){
        if(dp[n][j]>ans)
            ans = dp[n][j];
    }
    printf("%d", ans);
    return 0;
}
// 64 位输出请用 printf("%lld")