动态规划之买卖股票全解析【通俗易懂】

---

前言

买卖股票问题是动态规划中最经典的问题我把这一类问题分为两大类。一类是没有限制的，第二类是限制交易数的。

总的思路是记录好每天持有的还有每天不持有的，这两种状态即可。
他们的转移方程如下：
每一天的不持有状态是，可能是保持了前一天的不持有状态（不做操作而来的），或者由前一天的持有之后今天卖出去而来的。
每一天的持有状态是，可能保持前一天的持有状态而来。或者由今天的不持有且今天买入而来的。（由于dp[0[改变在先 所以是今天）
最后返回的都是最后一天不持有的状态。

一、无限制数

1、无限次买入卖出且无手续费

先来看看 无限次买入卖出 可以在同一天并且无手续费。
这个就是最基本的。
每一天的不持有状态是，可能是保持了前一天的不持有状态（不做操作而来的），或者由前一天的持有之后今天卖出去而来的。
每一天的持有状态是，可能保持前一天的持有状态而来。或者由今天的不持有且今天买入而来的。（由于dp[0[改变在先 所以是今天）

2、无限次买入卖出且无手续费，但是有冷冻期

有冷冻期（ 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。） 只需要记录前一天的不持有状态就行了 因为前一天不持有的 才能保证是前前天卖出去的，如果说用今天不持有的话，那么就可能是昨天卖出去的。

3、无限次买入卖出但是有手续费

有手续费 只需要在每一天卖出去的减去手续费

4、只能买卖一次

只能买卖一次 持有状态 不能由之前不持有的利润累加，就是持有状态永远都是0 - 今天的价格。

二、有限制数

先初始化 注意dp是k+1 遍历所有的天 每天遍历所有的交易次数情况。
记录好第一天进行了次交易的持有利润和不持有利润
同一天可以进行多次买入卖出所以第一天的交易数可以是1到k
第0次都为利润都为0
不持有的利润都未-prices[0]。
然后遍历每一天，与每一次交易。

剩余j次并且不持有 可能是之前剩余j次不持有的保持，也可能是剩余j次持有 在今天卖出
剩余j次并且持有 可能是之前剩余j次持有的保持，也可能是剩余j-1次不持有 在今天买入
第j笔交易 一定是在第j-1笔交易的基础上 进行的
买了才算一笔交易