买卖股票的最佳时机IV

描述

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路

可以使用动态规划求解该题。

首先可以将每天的交易状态分为下述情况：

• 没有过任何交易
• 进行过第1次买入
• 进行过第1次卖出
• 进行过第2次买入
• 进行过第2次卖出
• ……
• 进行过第n次买入
• 进行过第n次卖出 共有 $2k+1$ 个状态。

而每个状态之间存在下述转移关系：

\[本日进行过第i次买入的总利润=max\left( \begin{aligned} 昨日进行过第[i-1]次卖出的总利润 - 本日股价 \\ 昨日进行过第i次买入的总利润 \\ \end{aligned} \right)\] \[本日进行过第i次卖出的总利润=max\left( \begin{aligned} 昨日进行过第i次买入的总利润 + 本日股价 \\ 昨日进行过第i次卖出的总利润 \\ \end{aligned} \right)\]

通过动态规划按照上述状态与状态转移进行求解即可，最终获得的最大利润即为最后一天所有状态中的最大值。

上述方法同样适用于买卖股票的最佳时机III

代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp;

        for (const auto& price: prices) {
            dp.emplace_back(vector<int>(k * 2 + 1));
        }

        dp[0][0] = 0;
        for (size_t idx = 1; idx <= 2 * k; idx += 2) {
            dp[0][idx] = -prices[0];
            dp[0][idx + 1] = 0;
        }

        for (size_t day = 1; day < prices.size(); day++) {
            dp[day][0] = dp[day - 1][0];

            for (size_t idx = 1; idx <= 2 * k; idx += 2) {
                dp[day][idx] = max(dp[day - 1][idx - 1] - prices[day], dp[day - 1][idx]);
                dp[day][idx + 1] = max(dp[day - 1][idx] + prices[day], dp[day - 1][idx + 1]);
            }
        }

        return *max_element(dp.back().begin(), dp.back().end());
    }
};