股票问题还挺有意思的

[toc]

总共六道题

1笔交易 dp第二维有三个状态。这轮啥也不干 这轮买入 这轮卖出

n笔交易 dp第二维有两个状态。这轮持有股票 这轮没有持有股票

n笔交易 也是是否持有股票

LEECODE121.买卖股票的最佳时期

这题就是只能完成1笔交易

大体思路这两道简单题就是只要把dp数组定义好，思路就特别清晰了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
      #此轮啥也不干
      dp[[0 for _ in range(3)]for _ in range(n)]
      dp[0][0]=0
      #此轮买入股票
      dp[0][1]=(-1)*prices[0]
      #此轮卖出股票
      dp[0][2]=0
      ans=0
      for i in range(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]=dp[i-1][1]+prices[i]
      	ans = max(dp[i][0], dp[i][1],dp[i][2])
      return ans
    
1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        inf = int(1e9)
        minprice = inf
        maxprofit = 0
        for price in prices:
            maxprofit = max(price - minprice, maxprofit)
            minprice = min(price, minprice)
        return maxprofit

这样明显简洁多了

LEECODE122.买卖股票的最佳时期 (完成任意笔交易)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
      int n= prices.size();
      # 此轮没有股票 此轮持有股票
      in dp[n][2];
      dp[0][0]= 0,dp[0][1]=-prices[0];
      for (int i = 1; i < n; ++i) {
        # 这轮持有
      	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];

前面两题还算简单。

下面上点强度嗷。

123 309 188 714

123(只能完成两笔交易)

k=2

1
2
3
4
5
profit[i][j][k]
k是否持有股票 0 1
j交易了多少次 0 1 2
i第i天

309(有冷却)

188(最多进行k笔交易)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
mp[i][j][k]
i 第i天
j 是否持有股票
k 总共交易次数 注意这个交易次数 完成交易才算一次
#这一天卖的 或者前面卖的
# 先列状态转移方程
# 完成k-1笔 然后这笔卖出
# 完成k-1笔 然后现在买入
mp[i][k][0]= max(mp[i-1][k-1][1]+prices[i],mp[i-1][k][0])
mp[i][k][1]= max(mp[i-1][k-1][0]-prices[i],mp[i-1][k][1])

max(mp[n-1][0~k][0])

# k 改为 0 1 表示是否冷却

714(交易手续费)

参考:

覃超算法面试通关40讲