面试必刷TOP101：动态规划（78-82，Python实现）

78.打家劫舍（一）（小试牛刀）

78.1 动态规划

或许有人认为利用贪心思想，偷取最多人家的钱就可以了，要么偶数家要么奇数家全部的钱，但是有时候会为了偷取更多的钱，或许可能会连续放弃两家不偷，因此这种方案行不通，我们依旧考虑动态规划。

step 1：用 d p [ i ] dp[i] dp[i] 表示长度为 i i i 的数组，最多能偷取到多少钱，只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。
step 2：（初始状态） 如果数组长度为 1，只有一家人，肯定是把这家人偷了，收益最大，因此 d p [ 1 ] = n u m s [ 0 ] dp[1]=nums[0] dp[1]=nums[0]。
step 3：（状态转移） 每次对于一个人家，我们选择偷他或者不偷他，如果我们选择偷那么前一家必定不能偷，因此累加的上上级的最多收益，同理如果选择不偷他，那我们最多可以累加上一级的收益。因此转移方程为 d p [ i ] = m a x ( d p [ i − 1 ] , n u m s [ i − 1 ] + d p [ i − 2 ] ) dp[i]=max(dp[i−1],nums[i−1]+dp[i−2]) dp[i]=max(dp[i−1],nums[i−1]+dp[i−2])。这里的 i i i 在 d p dp dp 中为数组长度，在 n u m s nums nums 中为下标。

class Solution:
    def rob(self , nums: List[int]) -> int:
        # dp[i] 表示长度为 i 的数组，最多能偷多少钱
        dp = [0 for i in range(len(nums)+1)]
        # 初始状态
        dp[1] = nums[0]
        # 状态转移
        for i in range(2,len(nums)+1):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
        return dp[len(nums)]

时间复杂度： O ( n ) O(n) O(n)，其中 n 为数组长度，遍历一次数组。
空间复杂度： O ( n ) O(n) O(n)，动态规划辅助数组的空间。

79.打家劫舍（二）（小试牛刀）

79.1 动态规划

这道题与上一题比较类似，区别在于这道题是环形，第一家和最后一家是相邻的，既然如此，在原先的方案中第一家和最后一家不能同时取到。

step 1：使用原先的方案是：用dp[i]表示长度为i的数组，最多能偷取到多少钱，只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。
step 2：（初始状态） 如果数组长度为 1，只有一家人，肯定是把这家人偷了，收益最大，因此 d p [ 1 ] = n u m s [ 0 ] dp[1]=nums[0] dp[1]=nums[0]。
step 3：（状态转移） 每次对于一个人家，我们选择偷他或者不偷他，如果我们选择偷那么前一家必定不能偷，因此累加的上上级的最多收益，同理如果选择不偷他，那我们最多可以累加上一级的收益。因此转移方程为 d p [ i ] = m a x ( d p [ i − 1 ] , n u m s [ i − 1 ] + d p [ i − 2 ] ) dp[i]=max(dp[i−1],nums[i−1]+dp[i−2]) dp[i]=max(dp[i−1],nums[i−1]+dp[i−2])。这里的 i i i 在 d p dp dp 中为数组长度，在 n u m s nums nums 中为下标。
step 4：此时第一家与最后一家不能同时取到，那么我们可以分成两种情况讨论：

• 情况1：偷第一家的钱，不偷最后一家的钱。初始状态与状态转移不变，只是遍历的时候数组最后一位不去遍历。
• 情况2：偷最后一家的请，不偷第一家的钱。初始状态就设定了 d p [ 1 ] = 0 dp[1]=0 dp[1]=0，第一家就不要了，然后遍历的时候也会遍历到数组最后一位。

step 5：最后取两种情况的较大值即可。

class Solution:
    def rob(self , nums: List[int]) -> int:
        dp1 = [0 for i in range(len(nums)+1)]
        # 选择偷第 1 家
        dp1[1] = nums[0]
        # 则最后一家不偷
        for i in range(2,len(nums)):
            dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i-1])
        res1 = dp1[len(nums)-1]
        
        dp2 = [0 for i in range(len(nums)+1)]
        # 不偷第 1 家
        dp2[1] = 0
        # 则可以偷最后一家
        for i in range(2,len(nums)+1):
            dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i-1])
        res2 = dp2[len(nums)]
        
        return max(res1,res2)

时间复杂度： O ( n ) O(n) O(n)，其中 n 为数组长度，单独遍历两次数组。
空间复杂度： O ( n ) O(n) O(n)，动态规划辅助数组的空间。

80.买卖股票的最好时机（一）（小试牛刀）

80.1 动态规划

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

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

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]

时间复杂度： O ( n ) O(n) O(n)，其中 n 为数组长度，遍历一次数组。
空间复杂度： O ( n ) O(n) O(n)，动态规划辅助数组的空间。

80.2 贪心算法

如果我们在某一天卖出了股票，那么要想收益最高，一定是它前面价格最低的那天买入的股票才可以。因此我们可以利用贪心思想解决，每次都将每日收入与最低价格相减维护最大值。

step 1：首先排除数组为空的特殊情况。
step 2：将第一天看成价格最低，后续遍历的时候遇到价格更低则更新价格最低。
step 3：每次都比较最大收益与当日价格减去价格最低的值，选取最大值作为最大收益。

class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        res = 0
        if len(prices) == 0:
            return res
        min_price = prices[0]
        for i in range(1,len(prices)):
            min_price = min(min_price, prices[i])
            res = max(res, prices[i] - min_price)
        return res

时间复杂度： O ( n ) O(n) O(n)，其中 n 为数组长度，一次遍历数组。
空间复杂度： O ( 1 ) O(1) O(1)，常数级变量，无额外辅助空间。

81.买卖股票的最好时机（二）（小试牛刀）

81.1 动态规划

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

step 1：用 d p [ i ] [ 0 ] dp[i][0] dp[i][0] 表示第 i i i 天不持股到该天为止的最大收益， d p [ i ] [ 1 ] dp[i][1] dp[i][1] 表示第 i i i 天持股，到该天为止的最大收益。
step 2：（初始状态） 第一天不持股，则总收益为 0， d p [ 0 ] [ 0 ] = 0 dp[0][0]=0 dp[0][0]=0；第一天持股，则总收益为买股票的花费，此时为负数， d p [ 0 ] [ 1 ] = − p r i c e s [ 0 ] dp[0][1]=−prices[0] dp[0][1]=−prices[0]。
step 3：（状态转移） 对于之后的每一天：

• 如果当天不持股，有可能是前面的若干天中卖掉了或是还没买，因此到此为止的总收益和前一天相同，也有可能是当天卖掉股票，我们选择较大的状态 d p [ i ] [ 0 ] = m a x ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] + p r i c e s [ 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])；
• 如果当天持股，可能是前几天买入的还没卖，因此收益与前一天相同，也有可能是当天买入，减去买入的花费，同样是选取最大值： d p [ i ] [ 1 ] = m a x ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] − p r i c e s [ 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])。

class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        n = len(prices)
        # dp[i][0]：第 i 天不持股到该天为止的最大收益
        # dp[i][1]：第 i 天持股到该天为止的最大收益
        dp = [[0] * 2 for i in range(n)]
        # 初始状态
        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]

时间复杂度： O ( n ) O(n) O(n)，其中 n 为数组长度，遍历一次数组。
空间复杂度： O ( n ) O(n) O(n)，动态规划辅助数组相当于两个一维数组。

81.2 贪心思想

其实我们要想获取最大收益，只需要在低价买入高价卖出就可以了，因为可以买卖多次。利用贪心思想：只要一段区间内价格是递增的，那么这段区间的差值就是我们可以有的收益。

step 1：遍历数组，只要数组后一个比前一个更大，就可以有收益。
step 2：将收益累加，得到最终结果。

class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        res = 0
        for i in range(1,len(prices)):
            # 只要在某段递增就会有收益
            if prices[i-1] < prices[i]:
                res = res + (prices[i]-prices[i-1])
        return res

时间复杂度： O ( n ) O(n) O(n)，其中 n n n 为数组长度，遍历一次数组。
空间复杂度： O ( 1 ) O(1) O(1)，常数级变量，没有使用额外辅助空间。

82.买卖股票的最好时机（三）（小试牛刀）

82.1 动态规划

这道题与第80题的区别在于最多可以买入卖出2次，那实际上相当于它的状态多了几个，对于每天有到此为止的最大收益和持股情况两个状态，持股情况有了5种变化，我们用：

d p [ i ] [ 0 ] dp[i][0] dp[i][0] 表示到第 i i i 天为止没有买过股票的最大收益。
d p [ i ] [ 1 ] dp[i][1] dp[i][1] 表示到第 i i i 天为止买过一次股票还没有卖出的最大收益。
d p [ i ] [ 2 ] dp[i][2] dp[i][2] 表示到第 i i i 天为止买过一次也卖出过一次股票的最大收益。
d p [ i ] [ 3 ] dp[i][3] dp[i][3] 表示到第 i i i 天为止买过两次只卖出过一次股票的最大收益。
d p [ i ] [ 4 ] dp[i][4] dp[i][4] 表示到第 i i i 天为止买过两次同时也买出过两次股票的最大收益。

于是使用动态规划，有了如下的状态转移：
step 1：（初始状态） 与上述提到的题类似，第0天有买入了和没有买两种状态： d p [ 0 ] [ 0 ] = 0 dp[0][0]=0 dp[0][0]=0、 d p [ 0 ] [ 1 ] = − p r i c e s [ 0 ] dp[0][1]=−prices[0] dp[0][1]=−prices[0]。

step 2：状态转移： 对于后续的每一天:

• 如果当天还是状态 0，则与前一天相同，没有区别；
• 如果当天状态为 1，可能是之前买过了或者当天才第一次买入，选取较大值： d p [ i ] [ 1 ] = m a x ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] − p r i c e s [ 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])；
• 如果当天状态是 2，那必须是在 1 的状态下（已经买入了一次）当天卖出第一次，或者早在之前就卖出只是还没买入第二次，选取较大值： d p [ i ] [ 2 ] = m a x ( d p [ i − 1 ] [ 2 ] , d p [ i − 1 ] [ 1 ] + p r i c e s [ 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])；
• 如果当天状态是 3，那必须是在 2 的状态下（已经卖出了第一次）当天买入了第二次，或者早在之前就买入了第二次，只是还没卖出，选取较大值： d p [ i ] [ 3 ] = m a x ( d p [ i − 1 ] [ 3 ] , d p [ i − 1 ] [ 2 ] − p r i c e s [ 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]);
• 如果当天是状态 4，那必须是在 3 的状态下（已经买入了第二次）当天再卖出第二次，或者早在之前就卖出了第二次，选取较大值： d p [ i ] [ 4 ] = m a x ( d p [ i − 1 ] [ 4 ] , d p [ i − 1 ] [ 3 ] + p r i c e s [ 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 3：最后我们还要从0、第一次卖出、第二次卖出中选取最大值，因为有可能没有收益，也有可能只交易一次收益最大。

class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        n = len(prices)
        # 初始化 dp 为最小
        dp = [[-10000] * 5 for i in range(n)]
        # 初始状态
        dp[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(0, max(dp[n-1][2], dp[n-1][4]))

时间复杂度： O ( n ) O(n) O(n)，其中 n 为数组长度，只遍历一次数组。
空间复杂度： O ( n ) O(n) O(n)，动态规划二维辅助相当于 5 个一维数组。