[数据结构与算法]【编程之路】面试必刷TOP101：动态规划（78-82，Python实现）

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

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

78.1 动态规划

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

step 1：用 $dp[i]$ 表示长度为 $i$ 的数组，最多能偷取到多少钱，只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。
step 2：（初始状态） 如果数组长度为 1，只有一家人，肯定是把这家人偷了，收益最大，因此 $dp[1]=nums[0]$。
step 3：（状态转移） 每次对于一个人家，我们选择偷他或者不偷他，如果我们选择偷那么前一家必定不能偷，因此累加的上上级的最多收益，同理如果选择不偷他，那我们最多可以累加上一级的收益。因此转移方程为 $dp[i]=max(dp[i?1],nums[i?1]+dp[i?2])$。这里的 $i$ 在 $dp$ 中为数组长度，在 $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)$，其中 n 为数组长度，遍历一次数组。
空间复杂度：$O(n)$，动态规划辅助数组的空间。

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

79.1 动态规划

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

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

• 情况1：偷第一家的钱，不偷最后一家的钱。初始状态与状态转移不变，只是遍历的时候数组最后一位不去遍历。
• 情况2：偷最后一家的请，不偷第一家的钱。初始状态就设定了 $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)$，其中 n 为数组长度，单独遍历两次数组。
空间复杂度：$O(n)$，动态规划辅助数组的空间。

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

80.1 动态规划

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

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

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)$，其中 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)$，其中 n 为数组长度，一次遍历数组。
空间复杂度：$O(1)$，常数级变量，无额外辅助空间。

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

81.1 动态规划

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

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

• 如果当天不持股，有可能是前面的若干天中卖掉了或是还没买，因此到此为止的总收益和前一天相同，也有可能是当天卖掉股票，我们选择较大的状态 $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])$。

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)$，其中 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)$，其中 $n$ 为数组长度，遍历一次数组。
空间复杂度：$O(1)$，常数级变量，没有使用额外辅助空间。

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

82.1 动态规划

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

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

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

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

• 如果当天还是状态 0，则与前一天相同，没有区别；
• 如果当天状态为 1，可能是之前买过了或者当天才第一次买入，选取较大值：$dp[i][1]=max(dp[i?1][1],dp[i?1][0]?prices[i])$；
• 如果当天状态是 2，那必须是在 1 的状态下（已经买入了一次）当天卖出第一次，或者早在之前就卖出只是还没买入第二次，选取较大值：$dp[i][2]=max(dp[i?1][2],dp[i?1][1]+prices[i])$；
• 如果当天状态是 3，那必须是在 2 的状态下（已经卖出了第一次）当天买入了第二次，或者早在之前就买入了第二次，只是还没卖出，选取较大值：$dp[i][3]=max(dp[i?1][3],dp[i?1][2]?prices[i])$;
• 如果当天是状态 4，那必须是在 3 的状态下（已经买入了第二次）当天再卖出第二次，或者早在之前就卖出了第二次，选取较大值：$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)$，其中 n 为数组长度，只遍历一次数组。
空间复杂度：$O(n)$，动态规划二维辅助相当于 5 个一维数组。