代码随想录算法训练营第51天 | 714.买卖股票的最佳时机含手续费 309.最佳买卖股票时机含冷冻期 300.最长递增子序列

代码随想录系列文章目录

动态规划篇 —— 股票问题收尾、 线性dp开

---

---

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

题目链接
这道题和买卖股票2是一样的，两个状态，可以多次买卖但是只能持有一只股票
等于复习了

def maxProfit(self, prices: List[int], fee: int) -> int:
        dp = [[0] * 2 for _ in range(len(prices))]
        dp[0][0] = -prices[0] - fee
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]-fee) #持有
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]) #不持有
        return dp[-1][1]
1
2
3
4
5
6
7

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

题目链接

这个状态的定义有些多也有些乱说实话， 我试图捋一捋这些状态，但是刷一遍肯定是记不住的

这个题的base 还是买卖股票2， 相比于买卖股票2 多了一个 冷冻期；
就是在卖出股票之后，你不能立马买入股票，要有一天的冷冻期，这样的话状态的转移关系就变的不同了

1.状态定义

由于冷冻期的存在，这个题有四种状态

持有股票状态， 今天买入股票，或者是之前就买入了股票然后没有操作（状态1）

不持有股票状态，又分为两种状态：
两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态（状态2）
今天卖出了股票（状态3）

今天为冷冻期状态，但冷冻期状态不可持续，只有一天（状态4）

2.状态转移

持有股票的状态（状态1）， 分为前一天就持有，和今天买入

前一天就持有是 dp[i-1][0]
今天买入分为两种情况, 一种是昨天是冷冻期 dp[i-1][3] - prices[i]（状态4）
一种是昨天是保持股票卖出状态 dp[i - 1][1] - prices[i]（状态2）

dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i])

保持卖出股票状态（状态2）

前一天是状态2，或者前一天是冷冻期

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]

状态转移总结

dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - 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];
1
2
3
4

3.base case
除了第一个状态dp[0][0] = -prices[0]
其余都是初始化成0就行

4.遍历顺序以及解的位置
遍历顺序就正序就行

最后结果是取 状态二，状态三，和状态四的最大值，不少同学会把状态四忘了，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值

 max(dp[n - 1][3],max(dp[n - 1][1], dp[n - 1][2]))
1

代码

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

股票问题总结

代码随想录的总结

最长上升子序列

题目链接
1.状态定义
dp[i]定义为， 以i为结尾的序列的最长上升子序列的长度

2.状态转移
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

3.base case
初始化为1，因为单个的就是1

4.遍历顺序和解的位置
正序遍历
解的位置可能不在最后，需要在遍历i的时候动态维护一下

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