动态规划

动态规划是什么

《算法导论》对动态规划的说法：

动态规划方法通常用来求解 最优化问题 (optimization problem)。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。我们称这样的解为问题的 an optimal solution（合适解法之一），而不是 the optimal solution（唯一的最优解法），因为可能有多个解都达到最优值。

动态规划对每个子问题只求解一次，并将结果保存下来。如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算。因此，动态规划方法是付出额外的内存空间来节省计算时间，是典型的时空权衡（time-memory trade-of）的例子。

动态规划有两种等价实现方法：

带备忘的自顶向下发。
自底向上法。

动态规划解决股票问题

根据题目，可以思考：给定一个表示每天股票价格的数组，什么因素决定了可以获得的最大收益？

首先介绍一些符号：

用 n 表示股票价格数组的长度；
用 i 表示第 i 天（i 的取值范围是 0 到 n - 1）；
用 k 表示允许的最大交易次数；
用 T[i][k] 表示在第 i 天结束时，最多进行 k 次交易的情况下可以获得的最大收益。

在如果可以将 T[i][k]关联到子问题，例如T[i - 1][k]、T[i][k - 1]、T[i - 1][k - 1]等子问题，就能得到状态转移方程，并对这个问题求解。

如何得到状态转移方程呢？

最直接的办法是看第 i 天可能的操作。有多少个选项？答案是三个：买入、卖出、休息。

应该选择哪个操作？答案是：并不知道哪个操作是最好的，但是可以通过计算得到选择每个操作可以得到的最大收益。

关键点：

题目中确实有限制条件，规定不能同时进行多次交易。

决定在第 i 天买入，在买入之前必须持有 0 份股票；如果决定在第 i 天卖出，在卖出之前必须恰好持有 1 份股票。

持有股票的数量，是上文提及到的 隐藏因素 ，该因素影响第 i 天可以进行的操作，进而影响最大收益。

因此对 T[i][k]的定义需要分成两项：

T[i][k][0] 表示在第 i 天结束时，最多进行 k 次交易且在进行操作后，持有 0 份股票的情况下可以获得的最大收益；
T[i][k][1] 表示在第 i 天结束时，最多进行 k 次交易且在进行操作后，持有 1 份股票的情况下可以获得的最大收益。

使用新的状态表示之后，可以得到基准情况和状态转移方程。

基准情况：


T [-1][k][1] = -Infinity, 
T [i][0][1]  = -Infinity,

T[i][0][0]  = 0, 
T[-1][k][0] = 0,

基准情况中，i=0 表示第一天，i=-1 则还没开始。k=0 代表没有交易操作。

T[-1][k][0] = T[i][0][0] = 0 的含义，表示没有进行股票交易时，没有收益。

T[-1][k][1] = T[i][0][1] = -Infinity 的含义，是在没有进行股票交易时，不允许持有股票。

状态转移：


//第 i 天结束，最多 k 次交易后，有 0 份股票最大收益
T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])

//第 i 天结束，最多 k 次交易后，有 1 份股票最大收益。
T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k - 1][0] - prices[i])

T[i][k][0] ，因为代表最终 0 份股票，需要关联 i-1 天的状态，决定第 i 天进行的操作：

休息。在前一天，即第 i-1 天没有股票，第 i 天休息。对应：T[i - 1][k][0]
卖出。在前一天，即第 i-1 天持有股票，第 i 天卖出。对应：T[i - 1][k][1] + prices[i]

注意到允许的最大交易次数是不变的，因为每次交易包含两次成对的操作，买入和卖出。只有买入操作会改变允许的最大交易次数。

T[i][k][1] ，因为代表最终 1 份股票，需要关联 i-1 天的状态，决定第 i 天进行的操作：

休息。在前一天，即第 i-1 天持有股票，第 i 天休息。对应：T[i - 1][k][1]
买入。在前一天，即第 i-1 天没有股票，第 i 天买入。对应：T[i - 1][k-1][0] - prices[i]

注意到，买入时，允许的最大交易次数 减少1 次 ，因为每次买入操作会使用 1 次交易。

使用这种通用思路可以解决所有的股票问题。

动态规划的要素

基本状态/初始状态

状态转移方程

股票问题系列通解（转载翻译）

美版《股票问题通解》