算法动态规划

股票问题-自动机视角（自动机DP）

字数统计: 1k字   |   阅读时长: 3分
, ,

摘要: 本文介绍股票系列问题，从自动机的角度理解

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 股票系列问题-高维动态规划 中我们从高维动态规划的角度讨论了股票问题这个系列问题。

如果把操作序列看成字母表是 0(不操作), 1(买), 2(卖) 的字符串的话，自动机也是理解股票问题的很好的方式。

本文我们从这个系列问题最抽象的 188 为例，用自动机建模，并且最终可以回到动态规划（自动机DP）上。另外 5 个问题都是在 188 这个抽象问题的基础上增加一些条件的特定问题。最后我们给出自动机与动态规划的关系。

股票问题的自动机视角

自动机经常用于字符串匹配或识别，股票的操作序列也可以视为字符串。例如：”012102001002”，0 表示无操作，1 表示买，2 表示卖。因此可以考虑构造自动机识别这样的序列。

这股票系列的六个问题中，最抽象是 188。其它 5 个问题均是其特殊化或变种。

因此我们从问题 188. 买卖股票的最佳时机 IV 中抽象出自动机，然后再该自动机上推导算法，并且最终由回到了动态规划（自动机DP）。

下面我们先把问题描述一遍，然后直接给出从自动机出发的推导过程。直接从动态规划出发的方案在 股票系列问题-高维动态规划 中详细推倒过，这里不展开。

问题: 188. 买卖股票的最佳时机 IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

1
2
3
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

自动机的解决过程

(1) 抽象问题

给定价格表prices[0,…,n-1]，你需要刚好进行 k 笔交易。但有条件：必须先卖掉手里的股票，才能再卖新的股票。

抽象一个 “012” 的操作序列表示交易情况，则序列的条件如下：

  1. “012” 序列中任意一个 ‘1’ 之前的 ‘1’ 和 ‘2’ 的个数相等。任意一个 ‘2’ 之前的 ‘1’ 刚好比 ‘2’ 多一个
  2. 刚好有 k 个 ‘1’, k 个 ‘2’

(2) 定义自动机

定义 DFA $M = (S, \Sigma, f, S_{0}, F)$。

状态集合 $S$：

0 : 已经进行 0 次买卖
1 : 已经进行 1 次买0次卖
2 : 已经进行 1 次买卖
3 : 已经进行 2 次买1次卖
4 : 已经进行 2 次买卖
…
2k-1 : 已经进行 k 次买k-1次卖
2k : 已经进行 k 次买卖
-1: 非法

初始状态：0。

终结状态集合： {2k}。

字母表：{0, 1, 2}。

状态转移函数 $f$：。

该自动机识别的序列 seq 具有以下特性：

1、seq 中 1 和 2 的数量一致，且均为 k。
2、所有 1 和 2 形成的子序列中 1 和 2 是交替出现的。
3、所有 1 和 2 形成的子序列中 1 是开头字符。

一个 seq 表示的是一串的股票操作，能够被该自动机识别的 seq 就是一个合法的股票操作序列。

(3) 定义目标函数

仅仅识别出 seq 还没完，目标是求最大的利润(即手上的现金)。自动机可以识别的每个 seq 对应一个利润，现在要求这个利润的最大值。

定义：

1
2
3
4
profit(seq[i], i) := 第 i 天的时候进行 seq[i] 操作的利润
profit(0, i) = 0
profit(1, i) = -prices[i]
profit(2, i) = prices[i]

总利润表达式可以写成：

(4) 用自动机描述原问题

其中 $f(seq)=2k$，表示从 0 到 n - 1 的 seq 序列，读取到了 n - 1 且在 2k 状态(一直到 n - 1 均没有取到不合法的状态 -1)。

(5) 算法 - 寻找最优子结构

考虑 $\max\limits_{f(seq)=i} totalprofit(seq, n - 1)$，

此时的状态：[0..n-1] 上买卖总数共有 i 次(若 i 为偶数，则买卖各有 i/2 次，若 i 为奇数，则买有 $\frac{i + 1}{2}$ 次，卖有 $\frac{i - 1}{2}$ 次)。

该状态可能由两个来源转移而来，转移的时候，取两种情况中利润大的那一个。

(1) $\max\limits_{f(seq)=i-1} totalprofit(seq, n - 2) + profit(seq[n-1], n-1)$

[0..n-2] 上买卖总数有 i - 1 次，在 n - 1 上发生了一次买卖($seq[n-1]$为1或2)

(2) $\max\limits_{f(seq)=i} totalprofit(seq, n - 2)$

[0..n-2] 上买卖总数已经是 i 次，在 n - 1 无操作($seq[n-1] = 0$)。

其中 $profit(seq[n-1], n-1)$ 的取值需要分两种情况讨论：

  1. $i \mod 2 = 1$， $profit(1, n-1) = -prices[n-1]$
  2. $i \mod 2 = 0$， $profit(2, n-1) = prices[n-1]$

这是一个最优子结构，找到初始化方式后可以用动态规划。初始化如下：

(6) 算法 - 动态规划

记 $dp[i][j] := \max\limits_{f(seq)=i} totalprofit(seq, j)$

则动态规划算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
状态定义
dp[i][j] := [0..j] 上，买卖次数总和为 i 时的最大利润

状态转移
dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + prices[i])  i%2==0
         = max(dp[i][j-1], dp[i-1][j-1] - prices[i])  i%2==1

初始化
dp[0][j] = 0
dp[i][0] = 0           i%2==0
dp[i][0] = -prices[0]  i%2==1

答案
dp[2k][n-1]

(7) 代码 (C++)

这份代码实现前面 (1) ~ (7) 中从自动机推导出的动态规划算法。

正确性没有问题，但是输入 n=10000, k=1e9 时，dp 数组是 1e4 * 1e4 的，如果这种数据是存在的，会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(k == 0) return 0;
        int n = prices.size();
        if(n <= 1) return 0;
        int m = min(k * 2, n);
        vector<vector<int>> dp(m + 1, vector<int>(n, 0));
        for(int i = 0; i <= m; ++i)
            if(i % 2 == 1)
                dp[i][0] = -prices[0];
        for(int j = 1; j < n; ++j)
        {
            for(int i = 1; i <= m; ++i)
            {
                if(i % 2 == 0)
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + prices[j]);
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] - prices[j]);
            }
        }
        return dp[(m/2)*2][n - 1];
    }
};

另外5题与188的关系

  • 188 题是基础。
  • 121, 123 题是 188 题的具体化，即具体规定了有多少笔交易，也就是具体规定自动机的状态数目，而自动机形式完全相同。
  • 122 题是 188 题的一种极限状态下的形式，自动机的形式有比较大的变化。
  • 309 题对状态转移函数提出限制。
  • 714 题是修改了利润函数的计算。

总结：自动机 DP 与高维动态规划的关系

从最优化的角度，自动机与动态规划的关系大致如下：

对自动机识别的序列可以设计某种利润函数，然后将问题转换为求自动机可识别的序列中使得利润函数最优的最优化问题，如果该最优化问题在推导中发现了最优子结构，则可以回到动态规划上。

Share