最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

给定一个长度为 $N$ 的数组 $w$，数组的第 $i$ 个元素 $w_i$ 表示第 $i$ 天的股票 价格

一次买入一次卖出为一笔 合法交易，且不能同时产生多笔交易（必须在再次购买前出售掉之前的股票）

设计一个方案，使得总 合法交易数 不超过 $k$ 次，总利润最大

接 股票买卖II 的拓展思考

如果你做过前几版的 股票买卖 可以只看下面这几行的分析

AcWing 1055. 股票买卖 II DP + 贪心 双解 中分析过 第二版 的解法

而本题是 股票买卖 系列的 第四版

在 第二版 上， 额外 限制了 总交易的次数，因此 第二版 中的 贪心思路 不再适用

我们可以在 第二版 的 DP模型 上，额外加上记录 当前交易笔数 的参数即可

原题分析

对于第 $i$ 天 购入 的股票，当且经当第 $j(i \le j)$ 天才能 卖掉，获得的 利润 为 $w_j-w_i$

由此可知求解 股票交易 问题是一个 线性 的过程，于是我们思考一下能否用 线性DP 进行 状态记录 和 转移

线性DP如何记录当前的状态？

我们以当前递推到的天数，作为 线性DP 的阶段

对于递推到的第 $i$ 天来说，我们需要记录的信息有：

1. 在完成第 $i$ 天的决策后，状态是持仓($k=1$)还是空仓($k=0$)
2. 在第 $i$ 天交易完成时，总共完成的 完整 的交易数 $j$ (题目规定一次买入一次卖出是一笔 完整的交易)

那么如何利用该状态表示出题设中的状态转移行为呢？

1. 买入行为：k=0 $\rightarrow$ k=1
2. 卖出行为：k=1 $\rightarrow$ k=0
3. 持仓行为：k=1 $\rightarrow$ k=1
4. 空仓行为：k=0 $\rightarrow$ k=0

于是，有了如下的 闫氏DP分析法

闫氏DP分析法

状态表示$f_{i,j,k}$—集合： 考虑前 i 天的股票，第 i 天的 决策 是 k，且完成的 完整交易数 为 j 的方案

状态表示$f_{i,j,k}$—属性： 方案的总利润 最大MAX

状态计算$f_{i,j,k}$：

$$ \begin{cases} f_{i,j,0} = \max\Big( f_{i-1, j, 0}, f_{i-1, j - 1, 1} + w_i \Big) \\\ f_{i,j,1} = \max\Big( f_{i-1, j, 1}, f_{i-1, j, 0} - w_i \Big) \end{cases} $$

接下来用 状态机模型 解释一下状态计算

状态机模型DP

1. 第 i 天状态是持仓状态(j=1)，则第 i 天可能产生的行为是 买入行为 或 持仓行为
2. 第 i 天状态是空仓状态(j=0)，则第 i 天可能产生的行为是 卖出行为 或 空仓行为

【注】：卖出行为 会构成一次完整的交易，所以进行该类转移时， j 的参数也要变动

Code

时间复杂度： $O(N \times K)$

空间复杂度： $O(N \times K)$

初始状态: $f(0,0,0)$

目标状态: $f(n,j,0)\quad 其中 0\le j \le k$

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 110;

int n, k;
int w[N];
int f[N][M][2];

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

    memset(f, -0x3f, sizeof f);
    f[0][0][0] = 0; //初始状态f[0][0][0]

    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 0; j <= k; ++ j)
        {
            f[i][j][0] = f[i - 1][j][0];
            if (j) f[i][j][0] = max(f[i][j][0], f[i - 1][j - 1][1] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] - w[i]);
        }
    }

    int res = 0;
    for (int j = 0; j <= k; ++ j) res = max(res, f[n][j][0]); //目标状态f[n][j][0]

    cout << res << endl;

    return 0;
}

滚动数组优化

很多 线性DP 都可以用此类优化，详见 【01背包DP模型+朴素优化】

时间复杂度： $O(N \times K)$

空间复杂度： $O(K)$

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 110;

int n, k;
int w[N];
int f[2][M][2];

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

    memset(f, -0x3f, sizeof f);
    f[0][0][0] = 0; //初始状态f[0][0][0]

    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 0; j <= k; ++ j)
        {
            f[i & 1][j][0] = f[(i - 1) & 1][j][0];
            if (j) f[i & 1][j][0] = max(f[i & 1][j][0], f[(i - 1) & 1][j - 1][1] + w[i]);
            f[i & 1][j][1] = max(f[(i - 1) & 1][j][1], f[(i - 1) & 1][j][0] - w[i]);
        }
    }

    int res = 0;
    for (int j = 0; j <= k; ++ j) res = max(res, f[n & 1][j][0]); //目标状态f[n][j][0]

    cout << res << endl;

    return 0;
}