参考/优秀博客

图示

借用上面博客的一张图，来表题型的状态转移方程：
gupiao.png

该问题的不同情况分类

状态集合表示如下

  • dp[i][k][0]: 第i天结束时刻，允许的最大操作次数：k，手中不持有股票时，最大的收益
  • dp[i][k][1]: 第i天结束时刻，允许的最大操作次数：k，手中持有股票时，最大的收益

股票买卖考虑下面四种情况

  • 第i天结束时手中持有股票
    • 第i-1天结束时手中持有股票
    • 第i-1天结束时手中没有持有股票 (说明第i天买入了股票)
  • 第i天结束时手中没有持有股票
    • 第i-1天结束时手中持有股票 (说明第i天卖出了股票)
    • 第i-1天结束时手中没有持有股票

根据上面四种情况写转移方程

初始状态

1
2
dp[0][i][0] = 0
dp[0][i][1] = -price[0]  #因为这个表示，允许的最大操作次数是k，而不是实际操作次数，所以会出现dp[0][2][1]=1的情况

转移方程

1
2
dp[i][k][1] = max{dp[i-1][k][1], dp[i-1][k-1][0]-price[i]}			# 这里为什么是k-1? 因为第i天操作一次，那么第0~i-1天最多操作k-1次
dp[i][k][0] = max{dp[i-1][k][0], dp[i-1][k][1]+price[i]}

LeetCode中股票问题

题目 类型
121.买卖股票的最佳时机 限定交易次数 k = 1
122.买卖股票的最佳时机II 交易次数无限制
123.买卖股票的最佳时机III 交易次数 k = 2
188.买卖股票的最佳时机IV 交易次数最多为 k
309.买卖股票的最佳时机含冷冻期 含交易冷冻期
714.买卖股票的最佳时机含手续费 交易含手续费