前言

之前在刷leetcode的时候，遇到过一些有关股票售卖获利的问题，觉得挺有意思的，于是便写一篇博客来总结一下这类问题的解法，顺便复习一下动态规划。这些有关股票的问题有很多变种，其核心的问题是：给定每天的股票价格，怎么操作才能取得最大的获利？

动态规划

我只是简单介绍一下动态规划，因为这篇博客要解决的问题就是基于动态规划思想来求解的。如果想要深入了解动态规划，还是多学习《算法导论》然后多做题，最重要的是多思考，这样才能真正理解并运用动态规划来解决问题。

笼统地说，动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。从这个定义可以看出动态规划的本质，是对问题状态的定义和状态转移方程的定义。

状态

计算机的本质是一个状态机，内存里存储的所有数据构成了当前的状态，CPU只能利用当前的状态计算出下一个状态。当你企图使用计算机解决一个问题是，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据）以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少，所谓时间复杂度就是从初始状态到达最终状态中间需要多少步，也可以理解为在状态空间搜索最终状态的步数。

以上介绍的状态是所有算法问题里面都可以抽象出来的，而且不是所有的状态定义都可以使用动态规划来求解。要使用动态规划求解问题，我们定义的状态要满足2个性质：最优子结构和后无效性。

最优子结构：当前状态是由之前的某个或者某几个状态得到的
后无效性：当前状态得到之后，可以不用管之前是如何得到这个状态的

当然，我们还可以更加抽象一点：动态规划说到底就是在所有的状态空间中找到最优解的路径搜索问题。

balabala说了这么多，动态规划到底是个啥，大家可能还是似懂非懂，接下来我们利用动态规划来解决实际的问题，也就是本篇博客要解决的股票售卖获利的问题。

学以致用

重复一下，我们要解决的是哪类问题：给定每天的股票价格，怎么操作才能取得最大的获利？

建模

用数学语言描述一下(建模)：prices[]数组代表了每天的股票价格，长度为n，prices[i]代表第i天的股票价格(0<=i<=n-1)。接下来，我们来定义状态：k表示我们可以操作(售卖股票)的次数，T[i][k]表示最多操作k次的情况下，在第i天可以获得的最大利润。基于以上的建模，我们可以知道 T[-1][k] = T[i][0] = 0；

至此，T[i][k]能否代表问题的状态呢？先不着急，来看看我们每天能做的操作(状态转移方程)。在某一天，我们只能做一次操作，要不是买股票，要不是卖股票，要不就是无作为。根据题目的意思，想要买股票就必须之前是没有股票的情况才可以，同理想要卖股票必须是之前拥有股票才能可以卖。那么，基于此我们可以给出这类问题的状态的定义了：

T[i][k][0]：第i天操作结束后，在最多操作了k次并且不持有股票的情况下的最大的获利
T[i][k][1]：第i天操作结束后，在最多操作了k次并且持有股票的情况下的最大的获利

上述状态的定义是满足最优子结构和后无效性的，定义好了状态，状态转移方程就顺理成章了。

T[i][k][0] = Math.max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = Math.max(T[i-1][k][1], T[i-1][k-1][0] - prices[i])
T[-1][k][0] = 0 = T[i][0][0]； //0次操作或者第-1天的获利都是0
T[-1][k][1]= -Infinity = T[i][0][1]； //不可能出现的情况，视为负无穷

状态转移方程很直观，假设当天的最大获利我是不知道的，那么我就把我所有可能做的操作(买，卖，不作为)都试一次，然后在这些结果中找到最大的即可。我们要找的最终的结果就是T[prices.length-1][k][0]。

最后需要注意的是在状态的定义中设计到了操作次数，我们约定买和卖视为一次操作，统一在买操作的时候操作次数加1，为了避免误解，特此说明。

应用

leetcode上关于这类股票问题有以下几道：

以上的6道题，都可以使用以上的建模来解决，区别在于k值的不同，或者加上了不同的限制条件，万变不离其宗。

No.121 : k = 1

按照建模的状态定义与状态转移方程，很容易给出k=1时的情况：

T[i][1][0] = Math.max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = Math.max(T[i-1][1][1], T[i-1][1-1][0] - prices[i])=Math.max(T[i-1][1][1], - prices[i])

这里我们在求第i天的状态的时候，只用到了第i-1天的状态，故只需要保存之前一天的状态即可，空间复杂度为O(1)。


public int maxProfit_121(int[] prices) {
        int T_i10 = 0, T_i11 = Integer.MIN_VALUE;
        for (int price : prices) {
            T_i10 = Math.max(T_i10,T_i11 + price);
            T_i11 = Math.max(T_i11, 0 - price);
        }
        return T_i10;
    }

No.122 : k = +Infinity

同样，按照建模的方程，将k = +Infinity 代入：

T[i][k][0] = Math.max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = Math.max(T[i-1][k][1], T[i-1][k-1][0] - prices[i])=Math.max(T[i-1][k][1], T[i-1][k][0] - prices[i])

在循环的过程中，在修改T_ik0之前，需要临时保存一下，以便在求T_ik1的时候用到。


public int maxProfit_122(int[] prices) {
    int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
    for (int price : prices) {
        int temp = T_ik0;
        T_ik0 = Math.max(T_ik0, T_ik1 + price);
        T_ik1 = Math.max(T_ik1, temp - price);
    }
    return T_ik0;
}

No.123 : k = 2

状态转移方程：

T[i][k][0] = Math.max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = Math.max(T[i-1][k][1], T[i-1][k-1][0] - prices[i])

由于允许k=2，那么每天的状态包括 T_i20，T_i21，T_i10，T_i11，利用上述方程求解即可，注意要从T_i20，T_i21开始然后求T_i10，T_i11。这个顺序一般不能改变，具体原因会在更一般的情况中说明(k等于给定的输入值)。


public int maxProfit_123(int[] prices) {
    int T_i20 = 0;
    int T_i10 = 0;
    int T_i21 = Integer.MIN_VALUE;
    int T_i11 = Integer.MIN_VALUE;
    for (int price : prices) {
        T_i20 = Math.max(T_i20, T_i21 + price);
        T_i21 = Math.max(T_i21, T_i10 - price);
        T_i10 = Math.max(T_i10, T_i11 + price);
        T_i11 = Math.max(T_i11, -price);
    }
    return T_i20;
}

No.188 : k = 任意合法的输入值

这是最一般的情况了，每天的状态有[2*(k+1)]个，按照状态转移方程求解即可。同样，我们在求解第i天状态的时候，只需要用到i-1天的状态，那么在求每天的所有状态的时候按照k来遍历，顺序为k从大往小遍历，
这样就可以正确的利用到i-1天的状态了。如果还有印象的话，背包问题的简化写法也是异曲同工之妙。

如果k值超过了股票天数的二分之一，那么此时k值就和k = +Infinity的情况一样了，因为一次有效的交易操作，需要2天的时间。


public int maxProfit_188(int k1, int[] prices) {
        if (k1 == 0) {
            return 0;
        }
        if (k1 >= prices.length >>> 1) {//相当于k等于无穷大的情况，就是leetcode_122题
            int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
            for (int price : prices) {
                int T_ik0_old = T_ik0;
                T_ik0 = Math.max(T_ik0, T_ik1 + price);
                T_ik1 = Math.max(T_ik1, T_ik0_old - price);
            }
            return T_ik0;
        }
        int[] T_ik0 =new int[k1+1];
        int[] T_ik1 =new int[k1+1];
        Arrays.fill(T_ik1, Integer.MIN_VALUE);
        for (int price : prices) {
            //类似背包问题的简化写法，从后往前遍历！
            for (int k = 1 ; k <= k1; k++) {
                T_ik0[k] = T_ik0[k] > T_ik1[k] + price ? T_ik0[k] : T_ik1[k] + price;
                T_ik1[k] = T_ik1[k] > T_ik0[k - 1] - price ? T_ik1[k] : T_ik0[k - 1] - price;
            }
        }
        return T_ik0[k1];
    }

No.309 : k = +Infinity with cooldown

建模的状态转移方程如下：

T[i][k][0] = Math.max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = Math.max(T[i-1][k][1], T[i-1][k-1][0] - prices[i])

由于加入了”cooldown”机制，需要对状态转移方程做出修改。对于第i天，如果我们希望购买股票，那么i-1天是不能卖股票的，需要利用到第i-2天的信息，所以修改后的状态转移方程为：

T[i][k][0] = Math.max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = Math.max(T[i-1][k][1], T[i-2][k-1][0] - prices[i])


public int maxProfit_309(int[] prices) {
      int T_ik0 = 0;
      int T_ik1 = Integer.MIN_VALUE;
      int pre_T_ik0 = 0;//保存2天前的不持有股票的状态
      for (int price : prices) {
          int temp = T_ik0;
          T_ik0 = Math.max(T_ik0, T_ik1 + price);
          T_ik1 = Math.max(T_ik1, pre_T_ik0 - price);
          pre_T_ik0 = temp;
      }
      return T_ik0;
  }

No.714 : k = +Infinity with transaction fee

与122题大同小异，区别只在于我们售出股票的时候，利润要减去transaction fee(也可以在购买的时候减去transaction fee)。同时为了防止整数溢出，我们用到了long来过渡。

public int maxProfit_714(int[] prices, int fee) {
    long T_ik0 = 0;
    long T_ik1 = Integer.MIN_VALUE;
    for (int price : prices) {
        long temp = T_ik0;
        T_ik0 = Math.max(T_ik0, T_ik1 + price - fee);
        T_ik1 = Math.max(T_ik1, temp - price);
    }
    return (int)T_ik0;
}

总结

对于这类算法问题还是要多思考，多总结，最好还是兴趣为导向。