【ACWing】1057. 股票買賣 IV

題目位址：

https://www.acwing.com/problem/content/1059/

給定一個長度為 N N N的數組，數組中的第 i i i個數字表示一個給定股票在第 i i i天的價格。設計一個算法來計算你所能擷取的最大利潤，你最多可以完成 k k k筆交易。注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。一次買入賣出合為一筆交易。

輸入格式：

第一行包含整數 N N N和 k k k，表示數組的長度以及你可以完成的最大交易數量。第二行包含 N N N個不超過 10000 10000 10000的正整數，表示完整的數組。

輸出格式：

輸出一個整數，表示最大利潤。

資料範圍：

1 ≤ N ≤ 105 1≤N≤105 1≤N≤105

1 ≤ k ≤ 100 1≤k≤100 1≤k≤100

思路是動态規劃。可以将整個買賣過程視為一個狀态機接受一個輸入，狀态機有兩個狀态，分别是有股和無股，并且設 f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0]是到第 i i i天為止，一共恰好進行過 j j j次買入，并且第 i i i天結束時無股的情況下的最大利潤，設 f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1]是到第 i i i天為止，一共進行過 j j j次買入，并且第 i i i天結束時有股的情況下的最大利潤。設 p [ i ] p[i] p[i]是第 i i i天的股價，那麼就有：

1、今天的無股狀态，可以由昨天無股或者昨天有股轉移過來，如果昨天無股，那麼最大利潤是 f [ i − 1 ] [ j ] [ 0 ] f[i-1][j][0] f[i−1][j][0]；如果昨天有股，則是 f [ i − 1 ] [ j ] [ 1 ] + p [ i ] f[i-1][j][1]+p[i] f[i−1][j][1]+p[i]；

2、今天的有股狀态，也可以由昨天無股或者昨天有股轉移過來，如果昨天無股，那麼最大利潤是 f [ i − 1 ] [ j − 1 ] [ 0 ] − p [ i ] f[i-1][j-1][0]-p[i] f[i−1][j−1][0]−p[i]；如果昨天有股，則是 f [ i − 1 ] [ j ] [ 1 ] f[i-1][j][1] f[i−1][j][1]；

是以有： { f [ i ] [ j ] [ 0 ] = max ⁡ { f [ i − 1 ] [ j ] [ 0 ] , f [ i − 1 ] [ j ] [ 1 ] + p [ i ] } f [ i ] [ j ] [ 1 ] = max ⁡ { f [ i − 1 ] [ j − 1 ] [ 0 ] − p [ i ] , f [ i − 1 ] [ j ] [ 1 ] } \begin{cases}f[i][j][0]=\max\{f[i-1][j][0],f[i-1][j][1]+p[i]\} \\ f[i][j][1]=\max\{f[i-1][j-1][0]-p[i],f[i-1][j][1]\} \end{cases} {f[i][j][0]=max{f[i−1][j][0],f[i−1][j][1]+p[i]}f[i][j][1]=max{f[i−1][j−1][0]−p[i],f[i−1][j][1]}​考慮初始條件，一開始第 0 0 0天，隻有進行 0 0 0次買入并且無股的狀态是合法的，利潤是 0 0 0，是以 f [ 0 ] [ 0 ] [ 0 ] = 0 f[0][0][0]=0 f[0][0][0]=0，其餘情況都不合法，其轉移出來的狀态都不能作為答案，可以令 f [ 0 ] [ 0 ] [ 1 ] = f [ 0 ] [ . > 0 ] [ 0 ] = f [ 0 ] [ . > 0 ] [ 1 ] = − ∞ f[0][0][1]=f[0][.>0][0]=f[0][.>0][1]=-\infty f[0][0][1]=f[0][.>0][0]=f[0][.>0][1]=−∞。代碼如下：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010, K = 110;
int n, k;
int a[N], f[N][K][2];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int res = 0;
    // 這裡的優化的意思是，如果k >= n / 2，那麼等價于可以進行無限次交易
    if (k >= n / 2) {
        for (int i = 2; i <= n; i++)
            res += max(0, a[i] - a[i - 1]);

        cout << res << endl;
        return 0;
    }

    memset(f, -0x3f, sizeof f);
    f[0][0][0] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + a[i]);
            f[i][j][1] = f[i - 1][j][1];
            if (j >= 1) f[i][j][1] = max(f[i][j][1], f[i - 1][j - 1][0] - a[i]);
        }
    }

    cout << f[n][k][0] << endl;

    return 0;
}
           

時空複雜度 O ( N k ) O(Nk) O(Nk)。