当前位置：首页 > news >正文

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

news 来源：原创 2024/5/20 2:41:52

动态规划

思路：
- 状态定义
  - 假设 buy[i][j] 是第 i 天进行第 j 笔交易，手上还买入一支股票的最大利润；
  - sell[i][j] 是第 i 天进行第 j 笔交易的最大利润；
- 状态转移：
  - 第 i 天进行第 j 笔交易，手上还买入一支股票：
    - 第 i - 1 天即为此状态，第 i 天未进行操作，即 buy[i - 1][j]；
    - 第 i - 1 天进行第 j 笔交易，第 i 天买入，即 sell[i - 1][j] - prices[i]；
    - 则 buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i])；
  - 第 i 天进行第 j 笔交易：
    - 第 i - 1 天进行了第 j 笔交易，第 i 天未进行操作，即 sell[i - 1][j]；
    - 第 i - 1 天进行了第 j - 1 笔交易并且手上还持有一支股票，第 i 天进行卖出，即 buy[i - 1][j - 1] + prices[i]；
    - 则 sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i])；
- 初始状态：
  - buy[0][0] = -prices[0]
  - sell[0][0] = 0
  - 初始化第 0 天第 0 - k 笔交易值为 INT_MIN / 2；
    
    buy[0][i] = INT_MIN / 2;
    
    sell[0][i] = INT_MIN / 2;
- 最大交易次数为天数的一半，即 k = std::min(k, size / 2)；
- 第 0 笔交易的时候进行修正（避免 j - 1 溢出）
  
  buy[i][0] = std::max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
- 最大利润为最后一天完成交易的最大值：
  
  *std::max_element(sell[size - 1].begin(), sell[size - 1].end());

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int size = prices.size();if (0 == size) {return 0;}k = std::min(k, size / 2);std::vector<std::vector<int>> buy(size, std::vector<int>(k + 1));std::vector<std::vector<int>> sell(size, std::vector<int>(k + 1));buy[0][0] = -prices[0];sell[0][0] = 0;for (int i = 1; i <= k; ++i) {buy[0][i] = INT_MIN / 2;sell[0][i] = INT_MIN / 2;}for (int i = 1; i < size; ++i) {buy[i][0] = std::max(buy[i - 1][0], sell[i - 1][0] - prices[i]);for (int j = 1; j <= k; ++j) {buy[i][j] = std::max(buy[i - 1][j], sell[i - 1][j] - prices[i]);sell[i][j] = std::max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);}}return *std::max_element(sell[size - 1].begin(), sell[size - 1].end());}
};