题目描述
思路解析
一句话答案：LeetCode 188 买卖股票的最佳时机 IV：最多买卖 k 笔、求最大利润。逐笔状态 DP，第 j 笔各备 buy[j]、sell[j]，买接卖、卖接买递推，答案 sell[k]，O(n·k) 时间、O(k) 空间。
最多 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) 扫完。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条链：买j ← 卖(j−1)，卖j ← 买j。下面逐天滚动这四行。
顶行是每天股价（固定）。下面四行：买1/卖1/买2/卖2，待逐天填。买=持股现金，卖=已落袋利润。
第 0 天开局：买入就把现金垫成负数；还没卖出，所以两个「卖」都是 0。
填入第 0 天：买1=-2（垫了 2 那股），卖1=卖2=0（还没卖出）。
第 1 天（价格 4）：四个状态各看两条路。买j 接「卖(j−1) 后的钱减 p」，卖j 接「买j 加 p」——这条链把第 j 笔牢牢挂在第 j−1 笔之后。
各取较大值落子：买1 没变，卖1 今天卖出更优，买2 没变，卖2 今天卖出更优。第 1 天的卖2=2 是到今天「最多两笔」的最优。
第 2 天（价格 1）：四个状态各看两条路。买j 接「卖(j−1) 后的钱减 p」，卖j 接「买j 加 p」——这条链把第 j 笔牢牢挂在第 j−1 笔之后。
各取较大值落子：买1 改在今天买更划算，卖1 没变（今天卖不划算），买2 改用今天卖1的钱再买更划算，卖2 没变。第 2 天的卖2=2 是到今天「最多两笔」的最优。
第 3 天（价格 7）：四个状态各看两条路。买j 接「卖(j−1) 后的钱减 p」，卖j 接「买j 加 p」——这条链把第 j 笔牢牢挂在第 j−1 笔之后。
各取较大值落子：买1 没变，卖1 今天卖出更优，买2 没变，卖2 今天卖出更优。第 3 天的卖2=8 是到今天「最多两笔」的最优。
第 4 天（价格 5）：四个状态各看两条路。买j 接「卖(j−1) 后的钱减 p」，卖j 接「买j 加 p」——这条链把第 j 笔牢牢挂在第 j−1 笔之后。
各取较大值落子：买1 没变，卖1 没变（今天卖不划算），买2 没变，卖2 没变。第 4 天的卖2=8 是到今天「最多两笔」的最优。
第 5 天（价格 9）：四个状态各看两条路。买j 接「卖(j−1) 后的钱减 p」，卖j 接「买j 加 p」——这条链把第 j 笔牢牢挂在第 j−1 笔之后。
各取较大值落子：买1 没变，卖1 今天卖出更优，买2 没变，卖2 今天卖出更优。第 5 天的卖2=10 是到今天「最多两笔」的最优。
第 6 天（价格 3）：四个状态各看两条路。买j 接「卖(j−1) 后的钱减 p」，卖j 接「买j 加 p」——这条链把第 j 笔牢牢挂在第 j−1 笔之后。
各取较大值落子：买1 没变，卖1 没变（今天卖不划算），买2 改用今天卖1的钱再买更划算，卖2 没变。第 6 天的卖2=10 是到今天「最多两笔」的最优。
第 7 天（价格 8）：四个状态各看两条路。买j 接「卖(j−1) 后的钱减 p」，卖j 接「买j 加 p」——这条链把第 j 笔牢牢挂在第 j−1 笔之后。
各取较大值落子：买1 没变，卖1 没变（今天卖不划算），买2 没变，卖2 今天卖出更优。第 7 天的卖2=13 是到今天「最多两笔」的最优。
第 8 天（价格 12）：四个状态各看两条路。买j 接「卖(j−1) 后的钱减 p」，卖j 接「买j 加 p」——这条链把第 j 笔牢牢挂在第 j−1 笔之后。
各取较大值落子：买1 没变，卖1 今天卖出更优，买2 没变，卖2 今天卖出更优。第 8 天的卖2=17 是到今天「最多两笔」的最优。
最右下角的 卖2=17 就是最多两笔交易的最大利润——最后一定空仓最划算（手里别留股）。
边界先想清：k=0 或空数组答案恒 0，k 很大时退化成 LC122。
两个高频追问。
参考代码
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]复杂度
- 时间：O(n·k)，每天更新 k 对状态
- 空间：O(k)，只留 buy/sell 各 k+1 个
易错点
面试追问把动画讲成自己的话
追问和 LC123（最多两笔）什么关系？
追问k 很大时怎么优化？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
俄罗斯套娃信封问题
LeetCode 354 · 困难 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题