买卖股票的最佳时机 IV 图解题解

最多 k 笔交易，这道题在求什么

给数组 prices，prices[i] 是第 i 天股价，再给上限 k：最多买卖 k 笔（一买一卖算一笔，同时最多持一股），求最大利润。本课令 k 为 2、prices=[2,4,1,7,5,9,3,8,12]，答案 17：价 1 买价 9 卖赚 8，再价 3 买价 12 卖赚 9。

把 k 笔买卖日期全试一遍为什么不行

想暴力，就得从 n 天挑 2k 个买卖日、每笔买在卖前、笔笔不重叠，组合随 n 和 k 一起翻，稍大就试不完。退一步用区间递归，「前若干天做几笔」这类子问题也被反复重算。把子问题答案记下来只算一次，就是动态规划（把「前若干天、最多做几笔」的最优利润存进表，后面直接查）。

k 这一维怎么来，buy、sell 各存什么

先看只做 1 笔：盯买（正持股的现金）、卖（清仓后的利润）两个状态（状态=把当前局面压成几个关键数记下来）。至多 2 笔就是 123 那道题，翻倍成买1／卖1／买2／卖2。至多 k 笔无非把 2 换成 k：给第 j 笔（j 从 1 到 k）各备 buy[j]、sell[j]，「第几笔」被拎成下标，就是多出的 k 维。buy[j] 记做到第 j 笔还持股的最大现金，sell[j] 记已空仓的最大利润，答案落在 sell[k]。

买 j 为什么只能接卖 j−1

每天更新，两状态各看两条路取较大。buy[j] = max(buy[j], sell[j-1] - p)：要么维持昨天的持股，要么做完第 j−1 笔、手里攥着 sell[j−1] 后今天花 p 买进第 j 笔。第 j 笔的本金只能来自前 j−1 笔清仓后的钱，sell[j−1] 就是那笔钱，这条链把第 j 笔挂在第 j−1 笔身后，交易数天然超不了 k。sell[j] = max(sell[j], buy[j] + p) 则把这股卖掉落袋。

拿两笔上限这串价格亲手滚一遍

初始化 buy=[-inf,-inf,-inf]、sell=[0,0,0]（下标 0 占位，没买设成负无穷，没卖是 0）。逐天扫，内层 j 走 1 到 2。第 0 天价 2：buy[1]=-2、sell[1]=0，buy[2]=-2、sell[2]=0。第 2 天价 1：buy[2]=max(-2,2-1)=1，第 2 笔头一回用上第 1 笔的钱。sell[2] 逐天是 0、2、2、8、8、10、10、13，第 8 天价 12 时 sell[1]=11、buy[2]=5，sell[2]=max(13,5+12)=17，即最多两笔的最大利润。

k 一超过 n/2，这张 k 维的表为什么反而可以整个扔掉

外层扫 n 天、内层对 k 笔各更一对状态，时间 O(n·k)；只留 buy、sell 各 k+1 个格子滚动，空间 O(k)，不必铺整张二维表。两个边界要收干净。k 为 0 或 prices 为空时一笔都做不了，答案恒 0。另一头是 k 特别大，一笔至少占买、卖两天，n 天顶多做 n/2 笔，一旦 k≥n/2，上限形同虚设、题目退化成不限次数即 LC122，改用贪心（把每段上涨的差价吃进）一趟 O(n) 扫完。

Python

def maxProfit(k, prices):
    if not prices: return 0
    buy = [float("-inf")] * (k + 1)
    sell = [0] * (k + 1)
    for p in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j-1] - p)
            sell[j] = max(sell[j], buy[j] + p)
    return sell[k]

C++

int maxProfit(int k, vector<int>& prices){
    if(prices.empty()) return 0;
    vector<long> buy(k+1, LONG_MIN), sell(k+1, 0);
    for(int p : prices)
        for(int j = 1; j <= k; j++){
            buy[j] = max(buy[j], sell[j-1] - (long)p);
            sell[j] = max(sell[j], buy[j] + (long)p);
        }
    return (int)sell[k];
}

Java

int maxProfit(int k, int[] prices){
    if(prices.length == 0) return 0;
    long[] buy = new long[k+1], sell = new long[k+1];
    for(int j = 1; j <= k; j++) buy[j] = Long.MIN_VALUE / 2;
    for(int p : prices)
        for(int j = 1; j <= k; j++){
            buy[j] = Math.max(buy[j], sell[j-1] - p);
            sell[j] = Math.max(sell[j], buy[j] + p);
        }
    return (int)sell[k];
}