1057 股票买卖 IV（状态机模型-滚动数组优化）

蔚落 2022-08-28 13:45 122阅读 0赞

**1. 问题描述：**

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。

**输入格式**

第一行包含整数 N 和 k，表示数组的长度以及你可以完成的最大交易数量。第二行包含 N 个不超过 10000 的正整数，表示完整的数组。

**输出格式**

输出一个整数，表示最大利润。

数据范围

1 ≤ N ≤ 10 ^ 5，  
1 ≤ k ≤ 100

**输入样例1：**

3 2  
2 4 1

**输出样例1：**

**输入样例2：**

6 2  
3 2 6 5 0 3

**输出样例2：**

**样例解释**

样例1：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4 - 2 = 2 。  
样例2：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6 - 2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.  
来源：[https://www.acwing.com/problem/content/description/1059/][https_www.acwing.com_problem_content_description_1059]

**2. 思路分析：**

股票问题属于经典的**状态机问题**，状态机其实描述的是一个过程，可以将复杂的过程描述为状态之间的转移，根据题目的描述我们可以画出对应的状态机描述如下图所示（状态机描述是核心），我们可以声明一个三维数组或者三维列表，其中dp\[i\]\[j\]\[0\]表示前i天进行了j笔交易手中无货的状态，dp\[i\]\[j\]\[1\]表示前i天进行了j笔交易手中有货的状态（状态机其实是将普通的状态进一步划分为若干个具体的状态，这里是两个状态，这样状态之间的转移就非常清楚了），因为一次买入卖出为一笔交易，所以我们可以设置买入的时候为一笔交易的开始，当卖出的时候为一笔交易的结束，这样最终我们只需要统计手中无货的状态的最大值即可，所以在状态计算的时候需要注意当前状态是由上一次的第j次交易还是j - 1次交易得到的，因为我们设置了买入股票的时候为交易的开始，所以当我们计算到手中有货状态的时候应该是由上一个状态中的第j - 1次交易转移过程的，这样当手中有货的时候那么表示新的交易的开始。因为N和k都是比较大的，所以相乘的结果也是比较大的，而且考虑到每一次只是使用到了某一维的两种状态，所以我们可以使用滚动数组优化一下空复杂度，这样可以我们使用python语言来解决的时候其实是声明多维列表的时候才不会耗时太大导致超时的情况。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

**python（超时代码）：**

if __name__ == "__main__":
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        INF = 10 ** 10
        dp = [[[-INF] * 2 for i in range(k + 1)] for j in range(n + 1)]
        for i in range(n + 1): dp[i][0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, k + 1):
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + a[i - 1])
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - a[i - 1])
        res = 0
        for i in range(1, k + 1):
            res = max(res, dp[n][i][0])
        print(res)

**滚动数组优化：其实滚动数组的实现非常简单，先当做不滚动来写，然后与1做运算即可**

if __name__ == "__main__":
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        INF = 10 ** 10
        # 可以发现只是利用到了两个状态所以我们可以使用滚动数组来解决这样可以避免python声明很大的多维列表耗时很久的问题
        dp = [[[-INF] * 2 for i in range(k + 1)] for j in range(2)]
        for i in range(n + 1): dp[i & 1][0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, k + 1):
                dp[i & 1][j][0] = max(dp[(i - 1) & 1][j][0], dp[(i - 1) & 1][j][1] + a[i - 1])
                dp[i & 1][j][1] = max(dp[(i - 1) & 1][j][1], dp[(i - 1) & 1][j - 1][0] - a[i - 1])
        res = 0
        for i in range(1, k + 1):
            res = max(res, dp[n & 1][i][0])
        print(res)

[https_www.acwing.com_problem_content_description_1059]: https://www.acwing.com/problem/content/description/1059/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/7b2a003d64f945f29be05fc33216d2cb.png