重练算法（代码随想录版） day41 - 动态规划part8

今日刷题量：3
当前刷题总量：153
Easy: 60
Mid: 85
Hard: 8

Day41
解题思想

121/122/123区别只在于允许的交易次数，共同点-每天结束时只有持股和不持股两种情况，收益就是到当前为止的最大利润

121：最多 1 次交易

• 只能买一次卖一次
  • cash：不持股最大收益
  • hold：持股最大收益（只能来自一次买入）
• 转移（价格 p）：
  • cash = max(cash, hold + p)（卖或不卖）
  • hold = max(hold, -p)（买或不买，只能用初始 0 去买）
• 答案：cash

122：无限次交易

• 可以买卖很多次（但同一时间只能持一股）。
  • cash = max(cash, hold + p)
  • hold = max(hold, cash_old - p)（可以买入：用“昨天不持股的收益”再买）
• 答案：cash

123：最多 2 次交易

• 把“一次交易”拆成两步：买、卖。最多 2 次就对应 4 个状态：
  • buy1：第 1 次买后（持股）
  • sell1：第 1 次卖后（不持股）
  • buy2：第 2 次买后（持股）
  • sell2：第 2 次卖后（不持股）
• 更新（价格 p）：
  • buy1 = max(buy1, -p)
  • sell1 = max(sell1, buy1 + p)
  • buy2 = max(buy2, sell1 - p)
  • sell2 = max(sell2, buy2 + p)
• 答案：sell2

练习题目
121. 买卖股票的最佳时机（easy）：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
122.买卖股票的最佳时机II （mid）：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
123.买卖股票的最佳时机III（hard）：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/