0188. Best Time to Buy and Sell Stock IV ========================================= 题目信息 -------- :题号: 0188. 买卖股票的最佳时机 IV :难度: Hard :主题: 动态规划、交易状态机、滚动数组、贪心退化 :原题: `LeetCode 0188 `_ :重点: 用已完成交易数与持仓状态压缩买卖日期历史,并识别 k 足够大时的无限交易结构 题目重述 -------- 给定整数 ``k`` 和每日股价数组 ``prices``。最多完成 ``k`` 笔交易,每笔交易由一次买入和 之后的一次卖出组成;卖出前必须持股,任意时刻最多持有一股。 可以少做交易或完全不交易,返回能够获得的最大利润。 自建示例 -------- .. code-block:: text 输入:k = 2, prices = [3,2,6,5,0,3] 输出:7 2 买入、6 卖出获利 4;0 买入、3 卖出获利 3。 .. code-block:: text 输入:k = 1, prices = [3,2,6,5,0,3] 输出:4 交易额度只有一笔,不能同时取得两段上涨收益。 .. code-block:: text 输入:k = 10, prices = [1,2,3,4,5] 输出:4 交易额度已经不构成限制,整段上涨都可以收入。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: int unlimitedTransactions( const std::vector& prices) { int profit = 0; for (int day = 1; day < static_cast(prices.size()); ++day) { profit += std::max( 0, prices[day] - prices[day - 1]); } return profit; } int limitedTransactions( int limit, const std::vector& prices) { long long unreachable = std::numeric_limits::lowest() / 4; std::vector cash(limit + 1, unreachable); std::vector hold(limit + 1, unreachable); cash[0] = 0; for (int raw_price : prices) { long long price = raw_price; for (int completed = limit; completed >= 1; --completed) { if (cash[completed] != unreachable) { hold[completed] = std::max( hold[completed], cash[completed] - price); } if (hold[completed - 1] != unreachable) { cash[completed] = std::max( cash[completed], hold[completed - 1] + price); } } hold[0] = std::max(hold[0], cash[0] - price); } return static_cast( *std::max_element(cash.begin(), cash.end())); } public: int maxProfit(int k, std::vector& prices) { int days = static_cast(prices.size()); if (k <= 0 || days < 2) { return 0; } if (k >= days / 2) { return unlimitedTransactions(prices); } return limitedTransactions(k, prices); } }; 题解 ---- 枚举交易区间重复了哪些未来 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 一笔交易需要选择买入日、卖出日;多笔交易还要保证区间按时间排列且不重叠。枚举所有日期 组合会产生指数级动作序列。许多不同历史到达同一天时,其后合法选择其实只由三件事决定: 今天处理到哪里、已经完成几笔交易、当前是否持股。 过去具体在哪些日期买卖不再影响未来,只要保留该状态下能够达到的最大现金。动态规划用 这个最优值合并所有等价历史,删除对相同后缀的重复搜索。 交易数应该在何时增加 ~~~~~~~~~~~~~~~~~~~~ 定义处理完当前日期前缀后的状态: ``cash[t]`` 恰好完成 ``t`` 次卖出、当前空仓时的最大利润。 ``hold[t]`` 恰好完成 ``t`` 次卖出、当前持有一股时的最大现金。 一笔交易在卖出时才完成。因此买入从 ``cash[t]`` 转到 ``hold[t]``,坐标不变;卖出从 ``hold[t-1]`` 转到 ``cash[t]``,完成数增加一。若把买入也增加 ``t``,会把 ``k`` 错解 为动作次数,使一买一卖消耗两个额度。 状态转移只有“不操作”和“当天交易动作”: .. code-block:: text hold[t] = max(旧 hold[t], 旧 cash[t] - price) cash[t] = max(旧 cash[t], 旧 hold[t-1] + price) t >= 1 最多持有一股被状态结构直接保证:买入只能从空仓来,卖出只能从持股来。 不可达状态与最终答案 ~~~~~~~~~~~~~~~~~~~~ 处理任何价格前,只有 ``cash[0] = 0`` 合法:零次交易且空仓。正数交易状态和所有持股 状态都尚不可达,不能初始化为 0;否则算法会凭空卖出一股,或假装已经免费完成交易。 代码用安全的负无穷 ``unreachable`` 标记这些状态,并只从有限状态做加减。最终必须空仓, 但可以完成少于 ``k`` 笔交易,所以答案是所有 ``cash[t]`` 的最大值,而不是强迫返回 ``cash[k]``。``cash[0] = 0`` 也保证全程下降时可以选择不交易,利润不会为负。 原地更新顺序为何从大到小 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 状态数组跨日期滚动复用。当天对 ``completed`` 从 ``limit`` 递减到 1: * 更新 ``hold[completed]`` 时,``cash[completed]`` 尚未被当天卖出动作改写,仍是前一天 状态; * 更新 ``cash[completed]`` 时,依赖的 ``hold[completed-1]`` 位于更小下标,尚未轮到, 也仍是前一天状态; * 当前写入的大下标不会被之后更小下标的转移读取。 最后单独更新 ``hold[0]``。因此原地数组与为每天创建 ``nextCash``、``nextHold`` 完全 等价,没有把当天新状态串联成额外交易。若从小到大更新,``hold[t-1]`` 可能已经包含当天 买入,状态时间层就会混杂。 具体状态走读 ~~~~~~~~~~~~ 对 ``k = 1``、价格前缀 ``[3,2,6]``: .. code-block:: text 日期价格 hold[0] cash[1] 初始 不可达 不可达 3 max(不可达, 0-3) = -3 不可达 2 max(-3, 0-2) = -2 不可达 6 -2 max(不可达, -2+6) = 4 ``hold[0] = -2`` 表示在价格 2 买入后持股;价格 6 时卖出进入恰好一笔交易的空仓状态, 利润 4。完整示例继续扫描后,``hold[1]`` 会在第一笔交易完成后以价格 0 买入,最后卖出使 ``cash[2] = 7``。 k 足够大时约束为何消失 ~~~~~~~~~~~~~~~~~~~~~~ ``n`` 天最多完成 ``floor(n/2)`` 笔交易,因为每笔至少需要一个买入日和一个更晚卖出日。 当 ``k >= floor(n/2)``,任何合法交易策略都不会碰到额度上限,问题退化为无限交易。 此时把每个正相邻差加入利润: .. code-block:: text sum(max(0, prices[day] - prices[day-1])) 任意买入 ``i``、卖出 ``j`` 的利润等于区间相邻差之和,负差只会降低它,所以所有策略都 不可能超过全数组正差之和;把连续正差合并为一个上涨段,在段首买、段尾卖,就能达到这个 上界。上涨段数不超过 ``floor(n/2)``,当前额度足够。 这个分支既把时间从 ``O(nk)`` 降为 ``O(n)``,也避免在 ``k`` 很大时创建无意义的状态 数组。它只在交易限制确实失效时使用;小 ``k`` 无条件收集正差会超额交易。 正确性与复杂度 ~~~~~~~~~~~~~~ 有限分支的初始化准确描述空前缀;每个新状态穷尽“不操作、买入或卖出”的全部合法来源, 递减顺序保证来源属于前一天。归纳可知 ``cash/hold`` 始终符合定义,最终最大空仓状态就是 至多 ``k`` 笔交易的最优利润。无限分支由正差上界及上涨段可达性得到最优。 当限制有效时,时间复杂度为 ``O(nk)``、额外空间为 ``O(k)``;限制失效时,时间为 ``O(n)``、额外空间为 ``O(1)``。利润状态使用 ``long long`` 和远离下界的哨兵,避免不可达 值参与减法时溢出,最后按题目返回类型转换为 ``int``。