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

一. 题目背景

        假设你有一个数组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