一文教你股票买卖问题实用而装逼的解法

发布时间:2021-07-20 发表于话题:不同时间买的股票卖出的顺序 点击:42 当前位置:财神股票资讯网 美食 一文教你股票买卖问题实用而装逼的解法 手机阅读

「股票买卖问题」大概是每个刷 LeetCode 的同学都会遇到的一大拦路虎,特别是其中的第三道题。你是否也曾因为这道题而懵逼呢?

股票买卖系列问题

LeetCode 上的股票买卖系列问题一共六道,形成一个巨大的系列,蔚为壮观。系列的前两道题并不难,可以通过思维转换得到解法。然而就在你以为整个系列都可以循序渐进地做出来时,第三道题的难度陡然上升,让人猝不及防。

更令人沮丧的是,这样一道难题,打开讨论区,看到的却是一份异常装逼的题解代码:

public int maxProfit(int[] prices) {    if (prices.length == 0) return 0;    int s1 = Integer.MIN_VALUE, s2 = 0,         s3 = Integer.MIN_VALUE, s4 = 0;    for (int p : prices) {        s1 = Math.max(s1, -p);        s2 = Math.max(s2, s1 + p);        s3 = Math.max(s3, s2 - p);        s4 = Math.max(s4, s3 + p);    }    return Math.max(0, s4);}

WTF?? 这谜一样的四个变量 s1/s2/s3/s4 是怎么回事?这种计算方式怎么能体现题目中「最多买卖两次」的限制?

不要慌张。其实这类问题是有套路的,只要掌握了套路,你也一样能写出这样装逼的解法。这个套路也非常实用,几道股票买卖问题都可以用这个套路解出来。

这样实用而装逼的解法,今天就让我为你细细讲述。本文会介绍股票买卖问题的这个解法中涉及到的几个技巧:

动态规划子问题的状态拆解与状态机定义

DP 数组的特殊值定义

动态规划的空间优化技巧

问题解法

我们来求解最典型的股票问题(三),它是其他几道题目解法的基础:

LeetCode 123. Best Time to Buy and Sell Stock III(Hard)

给定一个数组,它的第 个元素是一支给定的股票在第 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

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

示例:

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

很多同学可能已经隐约想到这道题是用动态规划来解,但是一直想不出来合适的具体思路。

这道题最大的难点就在于其限制条件「最多完成两笔交易」。如何在动态规划中描述这个限制条件?如何记录股票买卖过程中的「不同状态」?其实,全部的答案就在我们上一篇文章中讨论的技巧:拆分动态规划的子问题

不记得上一篇文章内容的同学可以点这里回顾:

LeetCode 例题精讲 | 17 动态规划如何拆分子问题,简化思路

当然,如果你只想知道股票买卖问题的解法,可以直接往下看。

状态机定义

对于题目中「最多完成两笔交易」这个限制条件,我们可以理解成:股票买卖的过程,经历了不同的阶段

在一开始,限制是「最多完成两笔交易」;

做完一笔交易之后,限制变成「只做一笔交易」;

做完两笔交易之后,限制变成「不能再做交易」。

有的解法选择定义一个参数 来表示可以进行交易的数量。不过 的取值只有 2、1、0,却要给动态规划增加一个维度,不太划算。我们可以直接定义多个子问题来描述这些不同的阶段。

另外,题目中还有一个条件是「再次购买前必须卖掉之前的股票」,这实际上又给股票买卖过程划分了阶段。我们有「持有股票」和「不持有股票」两种状态。在持有股票的时候,只能卖出,不能买入。不持有股票的时候则反之。

总体来看,做两笔交易,则股票买卖的过程可以分为五个阶段

阶段可交易次数持股状态可买入/卖出02不持有可买入11持有可卖出21不持有可买入30持有可卖出40不持有可买入 股票买卖过程的五个阶段

对应这五个阶段,我们可以定义五个子问题,分别用 、 、 、 、 来表示。字母 s 代表状态,股票买卖阶段的变化,其实就是状态的转移。

例如在阶段 1,我们持有股票,此时如果卖出股票,则变成不持有股票的状态,进入阶段 2。

~ 之间的状态转移可以用下面这张图来表示:

子问题间的状态转移关系(状态机)

在每一天,我们既可以选择买入/卖出,又可以选择不进行买卖。选择买入或者卖出的话,就会进入下一个阶段,对应状态转移图中向右的边;选择不买卖的话,会继续待在当前阶段,对应状态转移图中的环路。

这就是所谓的「状态机 DP」。定义多个子问题,从另一个角度来看,就是子问题在不同的「状态」间跳来跳去。

在理解了子问题之间的关系之后,我们正式地定义一下子问题和递推关系:子问题 分别表示「前 天结束后,处于阶段 0/1/2/3/4 时,当前的最大利润」。那么我们有:

。因为阶段 0 时没有任何买入卖出。

。第 k 天处于阶段 1,可能是前一天处于阶段 1,或者是前一天处于阶段 0,然后买入了第 k 天的股票(利润减去 )。

。第 k 天处于阶段 2,可能是前一天处于阶段 2,或者是前一天处于阶段 1,然后卖出了第 k 天的股票(利润增加 )。

。分析同 。

。分析同 。

理解 DP 数组

在定义了子问题及其递推关系后,我们还需要搞清楚 DP 数组的计算顺序。

首先,由于 始终为 0,我们其实不需要计算,直接作为常数 0 代入即可。这样就只剩 / / / 四个子问题了。

四个子问题中, 的取值范围都是 。这样我们的 DP 数组是四个长度为 的一维数组,如下图所示。

DP 数组

接着是 DP 数组中的依赖关系:

DP 数组的依赖关系

可以看出,DP 数组的计算顺序是从左到右、从上到下。我们可以根据这个写出初步的题解代码:

// 注意:这段代码并不完整public int maxProfit(int[] prices) {    if (prices.length == 0) {        return 0;    }    int n = prices.length;    int[] s1 = new int[n+1];    int[] s2 = new int[n+1];    int[] s3 = new int[n+1];    int[] s4 = new int[n+1];    // 注意:这里还缺少 base case 的赋值    for (int k = 1; k 

本文来源:https://www.thyysj.com/info/553105.html

标签组:[股票] [动态规划] [状态机

热门话题

美食推荐文章

美食热门文章