而这里，我们不用递归思想进行穷举，而是利用「状态」进行穷举。我们具体到每一天，看看总共有几种可能的「状态」，再找出每个「状态」对应的「选择」。我们要穷举所有「状态」，穷举的目的是根据对应的「选择」更新状态。听起来抽象，你只要记住「状态」和「选择」两个词就行，下面实操一下就很容易明白了。
for状态1in状态1的所有取值：for状态2in状态2的所有取值：for...dp[状态1][状态2][...]=择优(选择1，选择2...)比如说这个问题，每天都有三种「选择」：买入、卖出、无操作，我们用buy,sell,rest表示这三种选择。但问题是，并不是每天都可以任意选择这三种选择的，因为sell必须在buy之后，buy必须在sell之后。那么rest操作还应该分两种状态，一种是buy之后的rest（持有了股票），一种是sell之后的rest（没有持有股票）。而且别忘了，我们还有交易次数k的限制，就是说你buy还只能在k>0的前提下操作。
很复杂对吧，不要怕，我们现在的目的只是穷举，你有再多的状态，老夫要做的就是一把梭全部列举出来。这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的rest的状态，我们不妨用1表示持有，0表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：
dp[i][k][0or1]0<=i<=n-1,1<=k<=Kn为天数，大K为最多交易数此问题共n×K×2种状态，全部穷举就能搞定。
for0<=i 我们想求的最终答案是dp[n-1][K][0]，即最后一天，最多允许K次交易，最多获得多少利润。读者可能问为什么不是dp[n-1][K][1]？因为[1]代表手上还持有股票，[0]表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。 记住如何解释「状态」，一旦你觉得哪里不好理解，把它翻译成自然语言就容易理解了。 二、状态转移框架现在，我们完成了「状态」的穷举，我们开始思考每种「状态」有哪些「选择」，应该如何更新「状态」。只看「持有状态」，可以画个状态转移图。 通过这个图可以很清楚地看到，每种状态（0和1）是如何转移而来的。根据这个图，我们来写一下状态转移方程： dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])max(选择rest,选择sell) 解释：今天我没有持有股票，有两种可能：要么是我昨天就没有持有，然后今天选择rest，所以我今天还是没有持有；要么是我昨天持有股票，但是今天我sell了，所以我今天没有持有股票了。 dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])max(选择rest,选择buy) 解释：今天我持有着股票，有两种可能：要么我昨天就持有着股票，然后今天选择rest，所以我今天还持有着股票；要么我昨天本没有持有，但今天我选择buy，所以今天我就持有股票了。这个解释应该很清楚了，如果buy，就要从利润中减去prices[i]，如果sell，就要给利润增加prices[i]。今天的最大利润就是这两种可能选择中较大的那个。而且注意k的限制，我们在选择buy的时候，把k减小了1，很好理解吧，当然你也可以在sell的时候减1，一样的。 现在，我们已经完成了动态规划中最困难的一步：状态转移方程。如果之前的内容你都可以理解，那么你已经可以秒杀所有问题了，只要套这个框架就行了。不过还差最后一点点，就是定义basecase，即最简单的情况。 dp[-1][k][0]=0解释：因为i是从0开始的，所以i=-1意味着还没有开始，这时候的利润当然是0。dp[-1][k][1]=-infinity解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。dp[i][0][0]=0解释：因为k是从1开始的，所以k=0意味着根本不允许交易，这时候利润当然是0。dp[i][0][1]=-infinity解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。把上面的状态转移方程总结一下： basecase：dp[-1][k][0]=dp[i][0][0]=0dp[-1][k][1]=dp[i][0][1]=-infinity 状态转移方程：dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])读者可能会问，这个数组索引是-1怎么编程表示出来呢，负无穷怎么表示呢？这都是细节问题，有很多方法实现。现在完整的框架已经完成，下面开始具体化。 三、秒杀题目第一题，k=1 直接套状态转移方程，根据basecase，可以做一些化简： dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][1][1]+prices[i])dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][0][0]-prices[i])=max(dp[i-1][1][1],-prices[i])解释：k=0的basecase，所以dp[i-1][0][0]=0。 现在发现k都是1，不会改变，即k对状态转移已经没有影响了。可以进行进一步化简去掉所有k：dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=max(dp[i-1][1],-prices[i])直接写出代码： intn=prices.length;int[][]dp=newint[n][2];for(inti=0;i for(inti=0;i //k==1intmaxProfit_k_1(int[]prices){intn=prices.length;//basecase:dp[-1][0]=0,dp[-1][1]=-infinityintdp_i_0=0,dp_i_1=Integer.MIN_VALUE;for(inti=0;i 第二题，k=+infinity 如果k为正无穷，那么就可以认为k和k-1是一样的。可以这样改写框架： dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])=max(dp[i-1][k][1],dp[i-1][k][0]-prices[i]) 我们发现数组中的k已经不会改变了，也就是说不需要记录k这个状态了：dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])直接翻译成代码： intmaxProfit_k_inf(int[]prices){intn=prices.length;intdp_i_0=0,dp_i_1=Integer.MIN_VALUE;for(inti=0;i 每次sell之后要等一天才能继续交易。只要把这个特点融入上一题的状态转移方程即可： dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i])解释：第i天选择buy的时候，要从i-2的状态转移，而不是i-1。翻译成代码： intmaxProfit_with_cool(int[]prices){intn=prices.length;intdp_i_0=0,dp_i_1=Integer.MIN_VALUE;intdp_pre_0=0;//代表dp[i-2][0]for(inti=0;i 每次交易要支付手续费，只要把手续费从利润中减去即可。改写方程： dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]-fee)解释：相当于买入股票的价格升高了。在第一个式子里减也是一样的，相当于卖出股票的价格减小了。直接翻译成代码： intmaxProfit_with_fee(int[]prices,intfee){intn=prices.length;intdp_i_0=0,dp_i_1=Integer.MIN_VALUE;for(inti=0;i k=2和前面题目的情况稍微不同，因为上面的情况都和k的关系不太大。要么k是正无穷，状态转移和k没关系了；要么k=1，跟k=0这个basecase挨得近，最后也没有存在感。 这道题k=2和后面要讲的k是任意正整数的情况中，对k的处理就凸显出来了。我们直接写代码，边写边分析原因。 原始的动态转移方程，没有可化简的地方dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])按照之前的代码，我们可能想当然这样写代码（错误的）： intk=2;int[][][]dp=newint[n][k+1][2];for(inti=0;i 还记得前面总结的「穷举框架」吗？就是说我们必须穷举所有状态。其实我们之前的解法，都在穷举所有状态，只是之前的题目中k都被化简掉了。这道题由于没有消掉k的影响，所以必须要对k进行穷举： intmax_k=2;int[][][]dp=newint[n][max_k+1][2];for(inti=0;i 这里k取值范围比较小，所以可以不用for循环，直接把k=1和2的情况手动列举出来也可以： dp[i][2][0]=max(dp[i-1][2][0],dp[i-1][2][1]+prices[i])dp[i][2][1]=max(dp[i-1][2][1],dp[i-1][1][0]-prices[i])dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][1][1]+prices[i])dp[i][1][1]=max(dp[i-1][1][1],-prices[i]) intmaxProfit_k_2(int[]prices){intdp_i10=0,dp_i11=Integer.MIN_VALUE;intdp_i20=0,dp_i21=Integer.MIN_VALUE;for(intprice:prices){dp_i20=Math.max(dp_i20,dp_i21+price);dp_i21=Math.max(dp_i21,dp_i10-price);dp_i10=Math.max(dp_i10,dp_i11+price);dp_i11=Math.max(dp_i11,-price);}returndp_i20;}有状态转移方程和含义明确的变量名指导，相信你很容易看懂。其实我们可以故弄玄虚，把上述四个变量换成a,b,c,d。这样当别人看到你的代码时就会一头雾水，大惊失色，不得不对你肃然起敬。 第六题，k=anyinteger 有了上一题k=2的铺垫，这题应该和上一题的第一个解法没啥区别。但是出现了一个超内存的错误，原来是传入的k值会非常大，dp数组太大了。现在想想，交易次数k最多有多大呢？ 一次交易由买入和卖出构成，至少需要两天。所以说有效的限制k应该不超过n/2，如果超过，就没有约束作用了，相当于k=+infinity。这种情况是之前解决过的。 直接把之前的代码重用： intmaxProfit_k_any(intmax_k,int[]prices){intn=prices.length;if(max_k>n/2)returnmaxProfit_k_inf(prices); int[][][]dp=newint[n][max_k+1][2];for(inti=0;i 四、最后总结本文给大家讲了如何通过状态转移的方法解决复杂的问题，用一个状态转移方程秒杀了6道股票买卖问题，现在想想，其实也不算难对吧？这已经属于动态规划问题中较困难的了。 关键就在于列举出所有可能的「状态」，然后想想怎么穷举更新这些「状态」。一般用一个多维dp数组储存这些状态，从basecase开始向后推进，推进到最后的状态，就是我们想要的答案。想想这个过程，你是不是有点理解「动态规划」这个名词的意义了呢？ 具体到股票买卖问题，我们发现了三个状态，使用了一个三维数组，无非还是穷举+更新，不过我们可以说的高大上一点，这叫「三维DP」，怕不怕？这个大实话一说，立刻显得你高人一等，名利双收有没有。 所以，大家不要被各种高大上的名词吓到，再多的困难问题，奇技淫巧，也不过是基本套路的不断升级组合产生的。只要把住算法的底层原理，即可举一反三，逐个击破。