力扣方法总结-----动态规划-----买卖股票的最佳时机系列题目_力扣买卖股票

一、动态规划

本文还是利用动态规划的思想解决一系列的股票问题。首先给出动态规划的五部曲：
**
（1）确定dp数组的含义
（2）确定转移方程
（3）确定初始化
（4）确定遍历顺序
（5）如果结果有误，打印DP数组日志，看是否与推断的吻合
**

二、买卖股票的最佳时机系列题目

1.力扣121 买卖股票的最佳时机

如何用动态规划的思想去分析题目呢？动态规划是要将原问题分解成一系列的子问题，并将重叠的子问题存储起来，避免重复计算相同的值。
（1）确定dp数组的含义 在本题中。将每一天的状态分为dp[i][0]和dp[i][1]两种，其中dp[i][0]代表第i天持有股票时，手里的最大金钱。dp[i][1]代表第i天不持有股票时，手里的最大金额。（第i天持有不代表第i天买入，第i天不持有不代表第i天卖出）

（2）确定转移方程
dp[i][0] = max(dp[i-1][0],-prices[i])
dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i])

（3）确定初始化
dp[i][0] = -prices[0]
dp[i][1] = 1

（4）确定遍历顺序
从前往后遍历

完整代码如下：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[ 0 for j in range(0,2)] for i in range(0,len(prices))]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        for i in range(1,len(prices)):
            dp[i][0] = max(dp[i-1][0], -prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
        return max(dp[len(prices) - 1][0],dp[len(prices) - 1][1])
1
2
3
4
5
6
7
8
9

代码的时间复杂度为O（n），空间复杂度为O（n）

提交通过记录如下

2.力扣122 买卖股票的最佳时机 II

这个题目与上一个题目的区别就是，上一个题目要求只能购买售出一次，而这个题目对于购买售出的次数没有要求。
（1）确定dp数组的含义 在本题中。将每一天的状态分为dp[i][0]和dp[i][1]两种，其中dp[i][0]代表第i天持有股票时，手里的最大金钱。dp[i][1]代表第i天不持有股票时，手里的最大金额。（第i天持有不代表第i天买入，第i天不持有不代表第i天卖出）

（2）确定转移方程
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])

（3）确定初始化
dp[i][0] = -prices[0]
dp[i][1] = 0

（4）确定遍历顺序
从前往后遍历

完整代码如下：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[ 0 for j in range(0,2)] for i in range(0,len(prices))]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        for i in range(1,len(prices)):
            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 max(dp[len(prices) - 1][0],dp[len(prices) - 1][1])
1
2
3
4
5
6
7
8
9

代码的时间复杂度为O（n），空间复杂度为O（n）

提过通过的截图如下

3.力扣123 买卖股票的最佳时机 III

这个题目与之前的题目区别是，要求最多买入卖出的次数为2。所以在定义状态时要有所改变。
（1）确定dp数组的含义 在本题中。将每一天的状态分为dp[i][0]，dp[i][1]，dp[i][2]，dp[i][3]，dp[i][4]五种，其中dp[i][0]代表第i天什么不做时，手里的最大金钱。dp[i][1]代表第i天第一次持有股票时，手里的最大金额。dp[i][2]代表第i天第一次不持有股票时，手里的最大金额。dp[i][3]代表第i天第二次持有股票时，手里的最大金额。dp[i][4]代表第i天第二次不持有股票时，手里的最大金额。（第i天持有不代表第i天买入，第i天不持有不代表第i天卖出）

（2）确定转移方程
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] + preices[i])
（3）确定初始化
dp[i][0] =0
dp[i][1] = -prices[i]
dp[i][3] = -prices[i]

（4）确定遍历顺序
从前往后遍历

完整代码如下：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[ 0 for j in range(0,5)] for i in range(0,len(prices))]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        dp[0][2] = 0
        dp[0][3] = -prices[0]
        dp[0][4] = 0
        for i in range(1,len(prices)):
            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 dp[len(prices) - 1][4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

代码的时间复杂度为O（n），空间复杂度为O（n）

提交结果如下：

4.力扣188 买卖股票的最佳时机 IV

这道题目与之前的题目区别是，限定了买入卖出次数为K值。

（1）确定dp数组的含义 在本题中。由于限定买入卖出次数为k，所以就会有2*k + 1种状态
dp[i][0]代表第i天什么不做时，手里的最大金钱。dp[i][n],n为奇数时，代表第（n+1）/ 2次持有股票时，手里的最大金钱。
dp[i][n],n为偶数数时，代表第（n）/ 2此不持有股票时，手里的最大金钱。

（2）确定转移方程
dp[i][0] = dp[i-1][0]
当n为奇数时，dp[i][n] = max(dp[i-1][n],dp[i-1][n-1] - prices[i])
当n为偶数时，dp[i][n] = max(dp[i-1][n],dp[i-1][n-1] + prices[i])

（3）确定初始化
dp[i][0] =0
当n为奇数时，dp[i][n] = -prices[i]
当n为偶数时，dp[i][n] = 0

（4）确定遍历顺序
从前往后遍历

完整代码如下

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        dp = [[0 for j in range(0,2*k + 1)] for i in range(0,len(prices))]
        for i in range(0,2*k + 1):
            if i % 2 == 0:
                dp[0][i] = 0
            else:
                dp[0][i] = -prices[0]
        for i in range(1,len(prices)):
            dp[i][0] = dp[i - 1][0]
            for j in range(1,2 * k + 1):
                if j % 2 == 0:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i])
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i])
        return dp[len(prices) - 1][2 * k]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度为O（nk），空间复杂度为O（nk）

提交结果如下

5.力扣309 最佳买卖股票时机含冷冻期

这道题目与之前的区别是，每卖出股票之后必须有冷冻期
（1）确定dp数组的含义 在本题中。dp[i][0] 代表第i天持有股票时，手里的最大金钱。dp[i][1]代表第i天不持有股票（刚好代表第i天卖出，第i+1天为冷冻期），dp[i][2]代表第i天不持有股票（其中第i天一定是上一个冷冻期之后的天数），dp[i][3]代表第i天为冷冻期。

（2）确定转移方程
dp[i][0] = max（dp[i-1][0],max(dp[i-1][2] - price[i],dp[i-1][3] - price[i])）
dp[i][1] = dp[i-1][0] + price[i]
dp[i][2] = max(dp[i-1][2],dp[i-1][3])
dp[i][3] = dp[i-1][1]

（3）确定初始化
dp[i][0] = -price[0]
dp[i][1] = 0
dp[i][2] = 0
dp[i][3] = 0

（4）确定遍历顺序
从前往后遍历

完整代码如下：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0 for j in range(0,4)] for i in range(0,len(prices))]
        dp[0][0] = -prices[0]
        for i in range(1,len(prices)):
            dp[i][0] = max(dp[i-1][0],max(dp[i-1][1] - prices[i], dp[i-1][3] - prices[i]))
            dp[i][1] = max(dp[i-1][1],dp[i-1][3])
            dp[i][2] = dp[i-1][0] + prices[i]
            dp[i][3] = dp[i-1][2]
        return max(dp[len(prices) - 1][0],dp[len(prices) - 1][1],dp[len(prices) - 1][2],dp[len(prices) - 1][3])
1
2
3
4
5
6
7
8
9
10

代码的时间复杂度为O（n），空间复杂度为O（n）

提交结果如下

6.力扣 714. 买卖股票的最佳时机含手续费

本题其实跟第122题差不多，思路一样，只是在转移方程的时候，需要多减去手续费即可。

（1）确定dp数组的含义 在本题中。将每一天的状态分为dp[i][0]和dp[i][1]两种，其中dp[i][0]代表第i天持有股票时，手里的最大金钱。dp[i][1]代表第i天不持有股票时，手里的最大金额。（第i天持有不代表第i天买入，第i天不持有不代表第i天卖出）

（2）确定转移方程
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] - fee)

（3）确定初始化
dp[i][0] = -prices[0]
dp[i][1] = 0

（4）确定遍历顺序
从前往后遍历

完整代码如下：

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        dp = [[0 for j in range(0,2)] for i in range(0,len(prices))]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        for i in range(1,len(prices)):
            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] - fee)
        return max(dp[len(prices) - 1][0],dp[len(prices) - 1][1])
1
2
3
4
5
6
7
8
9

代码的时间复杂度为O（n），空间复杂度为O（n）

提交结果如下