动态规划法——递进式教你运用代码题解《买卖股票的最好时机》

绝地灬酷狼 2024-04-07 15:28 9阅读 0赞

## 一. 题目背景 ##

> 假设你有一个数组prices，长度为n，其中prices\[i\]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益。

**动态规划基本思想：**

> 动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

--------------------

## 二. 买卖股票的最好时机(只能买一次和卖一次) ##

**要求：**

> 1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
> 
> 2.如果不能获取到任何利润，请返回0
> 
> 3.假设买入卖出均无手续费

> 数据范围：0≤n≤10^5，0≤val≤10^4
> 
> 要求：空间复杂度 O(1)，时间复杂度 O(n)

**思路：**

> 对于每天有到此为止的最大收益和是否持股两个状态，因此我们可以用动态规划。

**具体做法：**

>  *  step 1：用dp\[i\]\[0\]dp\[i\]\[0\]dp\[i\]\[0\]表示第i天不持股到该天为止的最大收益，dp\[i\]\[1\]dp\[i\]\[1\]dp\[i\]\[1\]表示第i天持股，到该天为止的最大收益。
>  *  step 2：**（初始状态）** 第一天不持股，则总收益为0，dp\[0\]\[0\]=0dp\[0\]\[0\]=0dp\[0\]\[0\]=0；第一天持股，则总收益为买股票的花费，此时为负数，dp\[0\]\[1\]=−prices\[0\]dp\[0\]\[1\] = -prices\[0\]dp\[0\]\[1\]=−prices\[0\]。
>  *  step 3：**（状态转移）** 对于之后的每一天，如果当天不持股，有可能是前面的若干天中卖掉了或是还没买，因此到此为止的总收益和前一天相同，也有可能是当天才卖掉，我们选择较大的状态dp\[i\]\[0\]=max(dp\[i−1\]\[0\],dp\[i−1\]\[1\]+prices\[i\])dp\[i\]\[0\] = max(dp\[i - 1\]\[0\], dp\[i - 1\]\[1\] + prices\[i\])dp\[i\]\[0\]=max(dp\[i−1\]\[0\],dp\[i−1\]\[1\]+prices\[i\])；
>  *  step 4：如果当天持股，有可能是前面若干天中买了股票，当天还没卖，因此收益与前一天相同，也有可能是当天买入，此时收益为负的股价，同样是选取最大值：dp\[i\]\[1\]=max(dp\[i−1\]\[1\],−prices\[i\])dp\[i\]\[1\] = max(dp\[i - 1\]\[1\], -prices\[i\])dp\[i\]\[1\]=max(dp\[i−1\]\[1\],−prices\[i\])。

**python动态规划代码解：**

class Solution:
        def maxProfit(self , prices: List[int]) -> int:
            n = len(prices)
            #dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
            dp = [[0] * 2 for i in range(n)] 
            #第一天不持股，总收益为0
            dp[0][0] = 0 
            #第一天持股，总收益为减去该天的股价
            dp[0][1] = -prices[0] 
            #遍历后续每天，状态转移
            for i in range(1, n): 
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
                dp[i][1] = max(dp[i - 1][1], -prices[i])
            #最后一天不持股，到该天为止的最大收益
            return dp[n - 1][0]

**python一般解：**

class Solution:
        def maxProfit(self , prices: List[int]) -> int:
            # write code here
            low = prices[0]
            odd = 0
            for i in range(1,len(prices)):
                if prices[i]>low:
                    odd = max(prices[i]-low,odd)
                else:
                    low = prices[i]
            return odd

--------------------

## 三. 买卖股票的最好时机(可多次购买) ##

**要求：**

> 1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
> 
> 2. 如果不能获取收益，请返回0
> 
> 3. 假设买入卖出均无手续费

> 数据范围： 1≤n≤1×10^5 ， 1≤prices\[i\]≤10^4
> 
> 要求：空间复杂度 O(n)，时间复杂度 O(n)
> 
> 进阶：空间复杂度 O(1)，时间复杂度 O(n)

**思路：**

> 这道题与上面的区别在于可以多次买入卖出。 但是对于每天还是有到此为止的最大收益和是否持股两个状态，因此我们照样可以用动态规划。

**具体做法：**

>  *  step 1：用dp\[i\]\[0\]dp\[i\]\[0\]dp\[i\]\[0\]表示第i天不持股到该天为止的最大收益，dp\[i\]\[1\]dp\[i\]\[1\]dp\[i\]\[1\]表示第i天持股，到该天为止的最大收益。
>  *  step 2：**（初始状态）** 第一天不持股，则总收益为0，dp\[0\]\[0\]=0dp\[0\]\[0\]=0dp\[0\]\[0\]=0；第一天持股，则总收益为买股票的花费，此时为负数，dp\[0\]\[1\]=−prices\[0\]dp\[0\]\[1\] = -prices\[0\]dp\[0\]\[1\]=−prices\[0\]。
>  *  step 3：**（状态转移）** 对于之后的每一天，如果当天不持股，有可能是前面的若干天中卖掉了或是还没买，因此到此为止的总收益和前一天相同，也有可能是当天卖掉股票，我们选择较大的状态dp\[i\]\[0\]=max(dp\[i−1\]\[0\],dp\[i−1\]\[1\]+prices\[i\])dp\[i\]\[0\] = max(dp\[i - 1\]\[0\], dp\[i - 1\]\[1\] + prices\[i\])dp\[i\]\[0\]=max(dp\[i−1\]\[0\],dp\[i−1\]\[1\]+prices\[i\])；
>  *  step4：如果当天持股，可能是前几天买入的还没卖，因此收益与前一天相同，也有可能是当天买入，减去买入的花费，同样是选取最大值：dp\[i\]\[1\]=max(dp\[i−1\]\[1\],dp\[i−1\]\[0\]−prices\[i\])dp\[i\]\[1\] = max(dp\[i - 1\]\[1\], dp\[i - 1\]\[0\] - prices\[i\])dp\[i\]\[1\]=max(dp\[i−1\]\[1\],dp\[i−1\]\[0\]−prices\[i\])。

**python动态规划代码解：**

class Solution:
        def maxProfit(self , prices: List[int]) -> int:
            n = len(prices)
            #dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
            dp = [[0] * 2 for i in range(n)] 
            #第一天不持股，总收益为0
            dp[0][0] = 0 
            #第一天持股，总收益为减去该天的股价
            dp[0][1] = -prices[0] 
            #遍历后续每天，状态转移
            for i in range(1, n): 
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
            #最后一天不持股，到该天为止的最大收益
            return dp[n - 1][0]

**python一般解：**

class Solution:
        def maxProfit(self , prices: List[int]) -> int:
            # write code here
            res = 0
            for i in range(1,len(prices)):
                if prices[i]> prices[i-1]:
                    res += (prices[i]-prices[i-1])
            return res

--------------------

## 四. 买卖股票的最好时机(可多次购买) ##

**要求：**

> 1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票  
> 2. 如果不能获取收益，请返回0  
> 3. 假设买入卖出均无手续费

> 数据范围：1≤n≤10^5，股票的价格满足 1≤val≤10^4
> 
> 要求: 空间复杂度 O(n)，时间复杂度 O(n)
> 
> 进阶：空间复杂度 O(1)，时间复杂度 O(n)

**思路：**

> 这道题与第一题的区别在于最多可以买入卖出2次，那实际上相当于它的状态多了几个，对于每天有到此为止的最大收益和持股情况两个状态，持股情况有了5种变化，我们用：
> 
>  *  dp\[i\]\[0\]dp\[i\]\[0\]dp\[i\]\[0\]表示到第i天为止没有买过股票的最大收益
>  *  dp\[i\]\[1\]dp\[i\]\[1\]dp\[i\]\[1\]表示到第i天为止买过一次股票还没有卖出的最大收益
>  *  dp\[i\]\[2\]dp\[i\]\[2\]dp\[i\]\[2\]表示到第i天为止买过一次也卖出过一次股票的最大收益
>  *  dp\[i\]\[3\]dp\[i\]\[3\]dp\[i\]\[3\]表示到第i天为止买过两次只卖出过一次股票的最大收益
>  *  dp\[i\]\[4\]dp\[i\]\[4\]dp\[i\]\[4\]表示到第i天为止买过两次同时也买出过两次股票的最大收益

> 于是使用动态规划，有了如下的状态转移

**具体做法：**

>  *  step 1：**（初始状态）** 与上述提到的题类似，第0天有买入了和没有买两种状态：dp\[0\]\[0\]=0dp\[0\]\[0\] = 0dp\[0\]\[0\]=0、dp\[0\]\[1\]=−prices\[0\]dp\[0\]\[1\] = -prices\[0\]dp\[0\]\[1\]=−prices\[0\]。
>  *  step 2：**状态转移：** 对于后续的每一天，如果当天还是状态0，则与前一天相同，没有区别；
>  *  step 3：如果当天状态为1，可能是之前买过了或者当天才第一次买入，选取较大值：dp\[i\]\[1\]=max(dp\[i−1\]\[1\],dp\[i−1\]\[0\]−prices\[i\])dp\[i\]\[1\] = max(dp\[i - 1\]\[1\], dp\[i - 1\]\[0\] - prices\[i\])dp\[i\]\[1\]=max(dp\[i−1\]\[1\],dp\[i−1\]\[0\]−prices\[i\])；
>  *  step 4：如果当天状态是2，那必须是在1的状态下（已经买入了一次）当天卖出第一次，或者早在之前就卖出只是还没买入第二次，选取较大值：dp\[i\]\[2\]=max(dp\[i−1\]\[2\],dp\[i−1\]\[1\]+prices\[i\])dp\[i\]\[2\] = max(dp\[i - 1\]\[2\], dp\[i - 1\]\[1\] + prices\[i\])dp\[i\]\[2\]=max(dp\[i−1\]\[2\],dp\[i−1\]\[1\]+prices\[i\])；
>  *  step 5：如果当天状态是3，那必须是在2的状态下（已经卖出了第一次）当天买入了第二次，或者早在之前就买入了第二次，只是还没卖出，选取较大值：dp\[i\]\[3\]=max(dp\[i−1\]\[3\],dp\[i−1\]\[2\]−prices\[i\])dp\[i\]\[3\] = max(dp\[i - 1\]\[3\], dp\[i - 1\]\[2\] - prices\[i\])dp\[i\]\[3\]=max(dp\[i−1\]\[3\],dp\[i−1\]\[2\]−prices\[i\]);
>  *  step 6：如果当天是状态4，那必须是在3的状态下（已经买入了第二次）当天再卖出第二次，或者早在之前就卖出了第二次，选取较大值：dp\[i\]\[4\]=max(dp\[i−1\]\[4\],dp\[i−1\]\[3\]+prices\[i\])dp\[i\]\[4\] = max(dp\[i - 1\]\[4\], dp\[i - 1\]\[3\] + prices\[i\])dp\[i\]\[4\]=max(dp\[i−1\]\[4\],dp\[i−1\]\[3\]+prices\[i\])。
>  *  step 7：最后我们还要从0、第一次卖出、第二次卖出中选取最大值，因为有可能没有收益，也有可能只交易一次收益最大。

> ps：因为状态转移的时候，辅助数组只使用到了第i列和第i-1列，因此可以不使用数组，直接用变量代替，优化空间复杂度。

**python动态规划代码解：**

class Solution:
        def maxProfit(self , prices: List[int]) -> int:
            n = len(prices)
            #初始化dp为最小
            dp = [[-10000] * 5 for i in range(n)] 
            #第0天不持有状态
            dp[0][0] = 0 
            #第0天持有股票
            dp[0][1] = -prices[0] 
            #状态转移
            for i in range(1, n): 
                dp[i][0] = dp[i - 1][0]
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
                dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
                dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])
            #选取最大值，可以只操作一次
            return max(dp[n - 1][2], max(0, dp[n - 1][4]))

**python一般解：**

class Solution:
        def maxProfit(self , prices: List[int]) -> int:
            # write code here
            buy1,buy2 = 1e9,1e9
            sell1,sell2 = 0,0
            for i in prices:
                buy1 = min(buy1,i)
                sell1 = max(sell1,i-buy1)
                buy2 = min(buy2,i-sell1)
                sell2 = max(sell2,i-buy2)
            return sell2