深度挖掘动态思想

写在前面的话

本文从六个经典的股票问题出发，深度挖掘动态的思想，旨在理解动态思想的本质，灵活的处理各类动态规划的问题。这六个股票问题断断续续的耗费了几天的时间，初次解决这些问题，使用的是贪心的思想，时间和空间复杂度还算可以，但是这些思想中的联系不是很大，并不适合解决一系列的问题，在最后一个股票中，发现贪心的思想无从运用，于是最后是以三维的动态规划解决，当然效率方面不是很理想，最终，偶然看到了一篇英文的题解，将六个问题联系到一起，给出一个通用的解决办法，彻底打开了我的思路，于是不断的思考动态的核心思想，理解了一些，于是在此分享出来，本文最原始的思路从一篇英文的题解中获得（下面会给出具体链接），我没有照搬这种方式，而是以这个为最原始的思路，换一种正常的思考方式去不断的探索这些问题，本文就是我的探索历程和心得。 参考的题解链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems 本文所有代码采用C++ 本人水平不足，博客中难免存在一些问题，欢迎各位批评指正

---

本篇博客翻译自我的第一篇英文博客 ：
Buy and Sell Stock Issues–Deep Mining Dynamic Thinking

---

0x01.六个股票问题

问题一：（只进行一次交易）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

问题二：（交易次数不限）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

问题三：（含冷冻期）

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

问题四：（含手续费）

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。

问题五：（最多两笔交易）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

问题六：（指定最多交易次数）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

---

TIP：上述题目均来源于Leetcode 题目链接：戳我前往

---

0x02.基于动态规划分析问题

1 – 共性抽取

上述问题看起来具有很大的相似性，其最终所求都是所获得的利润最大值，所以，这些问题，一定具有某些共同点。
经过分析，我们能够得到以下共性：

• 给出的数组含义相同，均代表第 i 天的价格。
• 最终所求相同，都是所获得利润得最大值。
• 一次交易包括买入和卖出（这点很重要）。
• 买入必须在卖出之前。

2 – 异性比较

这些问题得不同之处，就是我们着手的根本点，我们需要分析出不同的本质是什么。
经过分析，我们能够得出以下的不同：

• 最多允许买卖的次数不同（最根本的不同）。
• 交易的状态不同（有些需要手续费，有些有冷冻期）。

3 – 问题多变一

为了达到将这些问题简化为一个问题的目的，我们需要做的就是异性转变为共性。
如何将异性变成共性呢，这就可以用到动态的思想，如果我们将最多允许的买卖次数设为一个变量 k，那么这些问题就都可以看成k 具体赋值后的问题，也就是说，最多允许买卖的次数为k的股票问题，就是这些问题的根问题，我们只要可以解决根问题，那么这些子问题，只需要根绝相应的条件转变就行了。

4 – 动态规划的第一步思考：状态是什么？

现在我们的问题转变为根问题，确定使用动态规划的思想后，第一步需要思考的就是：状态是什么？
怎么去理解这些状态呢？

• 第一，看哪些属性会对结果造成影响，如果对结果造成了影响，那就在动态思考的时候，肯定要作为状态考虑进去。
• 第二，看处于某一天的时候，有何选择，动态规划是一个择优的过程，这些选择，就是择优的依据。

现在我们按照这两个思路去思考：

• 给出的是一个数组，数组的内容是某一天的股票价格，因为买和卖是有先后顺序的，所以，对于这个具体的天数，肯定是会影响最终的结果的，第一个状态：日期。
• 题目中还有一个属性，就是最多允许买卖的次数，对于不同的次数，肯定会造成结果的不同，所以我们可以得出，第二个状态：最多允许买卖的次数。
• 然后我们去思考在具体的某一天，有什么选择，对于股票，我们只可能有两种情况，一种是有，一种就是没有，在某一天，你有股票和没有股票，肯定结果不相同，所以，这就可以得出，第三个状态：持仓还是空仓。

我们确定了状态之后，其实就可以写出状态的相应数组表示形式，三个状态，理应对应一个三维的数组：

• DP[i][j][k] //表示在第 i 天， j 次买卖，处于状态 k 下的最大获利值。
• 由于状态 k 的范围有限，就只有两种，我们可以采用相应的标志变量的形式一一列举。
• DP[i][j][0] //表示在第 i 天，最多允许 j 次买卖，手里没有股票的时候，最大获利值。
• DP[i][j][1] //表示在第 i 天，最多允许 j 次买卖，手里有股票的时候，最大获利值。
• 这是针对于这个问题最好的理解方式，在充分掌握了这个思路的前提下，可以降维。
• 不要看是一个三维数组，其实第三维度就相当于一个标志变量，可以降维。
• 有三个状态的问题，最好先用三维的方式表示出来，便于理解
• 确定了状态表达式之后，我们需要求的结果就是 DP[i][k][0] //在最后一天，最多允许 k 次买卖，且手里没有股票的情况下，最大获利值，也就是我们需要求出的答案
• 这个最多允许买卖次数 j 在数组中也可以理解为当前已经进行了j次交易。

这里还涉及到一个很重要的问题，就是，买入和卖出算一次交易，那么什么时候算一次交易完成，交易数加1呢，一般都以卖出算交易结束，这里采用这种方式，其实买入就算一次交易也可以，不过数组的相应含义要改变。

5 – 动态规划的第二步思考：状态转移方程？

确定了状态之后，我们需要确定状态转移方程，也是动态规划最核心的内容。
首先，我们要确定这是求一个最大值的问题，那么状态转移的时候，应该是一个择优的过程，而如何择优，就是转移方程的根本。

• 对于 DP[i][j][0] 来说，这个时候手里没有股票，手里没有股票是怎么造成的呢？一种情况就是之前也没有，到了第 i 天，仍然不买；还有一种情况就是，之前有股票，到了今天，卖了。
• 对于DP[i][j][1] 来说，这个时候手里有股票，手里的股票是哪里来的呢？一种情况就是之前就有，到了第 i 天，不作为，所以手上有股票；还有一种情况就是，之前没得股票，到了第 i 天，买入了股票，所以就有股票了。

对于每一种状态，都有两个选择，我们要从中找到能产生最大价值的一种，就是一个择优的过程，如何择优？取每种选择产生的价值中的最大值，就可以了。

• 对于 DP[i][j][0] 来说，应该选择不买和卖了中的最大值，不买的话，产生的价值是
  DP[i-1][j][0](就是上一天没有股票的时候的价值)，买的话，产生的价值是
  DP[i-1][j][1]+prices[i]（就是上一天有股票的时候的价值加上卖出去的价值)。
• 对于DP[i][j][1] 来说，就是选择不卖和买入中的最大值，不卖的话，产生的价值是
  DP[i-1][j][1]（就是上一天有股票的时候的价值），买入的话，产生的价值是
  DP[i-1][j-1][0]-prices[i]（就是上一天进行j-1次买卖之后，手里没有股票的价值减去买股票的花费）。
• 综上分析，转移方程为：
• DP[i][j][0]=max(DP[i-1][j][0],DP[i-1][j][1]+prices[i])
• DP[i][j][1]=max(DP[i-1][j][1],DP[i-1][j-1][0]-prices[i])

6 – 动态规划思考的第三步：初始条件？

前两个问题解决了，只要找到初始条件，就能写出代码了。
当i=0时，肯定不能运用这个方程，因为i=-1不能访问数组下标，我们求解的循环肯定是从1开始的，所以初始状态就是第0天，也就是i=0的情况。
初始条件如下：

• DP[0][j][0]=0 //第一天，手里没有股票，价值是0
• DP[0][j][1]=-prices[0] //第一天买入了股票，本来就没钱，现在欠了prices[i]

另外，j其实也存在一个临界条件，就是当j=0时，是不可能存在交易的（实际的j确实要大于0，但是在循环的过程中，就会出现j-1的情况，所以我们需要提前将这个值设定好）

• DP[i][0][0]=0 //不允许交易的情况下，没有股票，产生的价值就是0
• DP[i][0][1]=INT_MIN //不允许交易的情况下，不可能持有股票，采用INT_MIN的原因就是，在取最大值的时候直接无视掉这一值，不考虑它产生的影响

有了动态规划的这三个思想，等于这个问题已经被我们解决了，现在，只需要到具体问题中，再优化以下代码就可以了。

6 – 如何将动态规划的思想放于代码中？

我们前面说到，这是个最大值问题，也就是一个择优的过程，因为每个状态都有可能影响最终的结果，所以我们要充分考虑所有可能的情况，也就是说，要遍历到所有的情况，再在所有的情况中选择出最佳的答案。
单纯看根问题来说，有三种状态，要遍历所有状态，肯定需要三重循环，三重循环就已经可以遍历到所有可能的情况了。这里最内层循环就是0和1，所有可以不用循环一次。

这个三层循环只不过是解决根问题的最基本方法，当然可以在实际中，优化，省去没必要的时间和空间。

下面看一下根问题的解决代码：（前面还含有初始条件）

for (int i = 1; i < prices.size(); i++) {
    for (int j = k; j >= 1; j--) {
           DP[i][j][0] = max(DP[i - 1][j][0], DP[i - 1][j][1] + prices[i]);
           DP[i][j][1] = max(DP[i - 1][j][1], DP[i - 1][j - 1][0] - prices[i]);
      }
}
        

---

接下来，我们可以根据这一思想，到具体的问题中去实践了。

---

0x03.解决问题一（只进行一次交易）

1 – 子问题在根问题中情形：

第一个问题中，只进行一次买卖，说明是根问题k=1的情况，因为k取唯一值，所以，我们可以直接省去这一状态，全部按照买卖一次的情况算，根据这个思想，我们可以写出代码。

2-- 运用动态规划思想写出最初代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 0) return 0;
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], -prices[i]);
        }
        return dp[n - 1][0];
    }
};

解释：

• 这里省去了k=1这一恒定条件，所以相应的初始化也默认了。
• 计算dp[i][1]的那行，-prices[i]本应为0-prices[i]。

这段代码其实也相当于只用了一维数组，空间复杂度为 O（N），时间复杂度为O（N）。
但我们仔细一想，每次循环时，dp[i][0]和dp[i][1]都只和dp[i-1]有关，所以我们还可以把这个数组优化掉，采用两个变量来记录上一次的值。

3 – 状态压缩，最简代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 0) return 0;
        int dp0 = 0, dp1 = INT_MIN;
        for (int price:prices) {
            dp0 = max(dp0, dp1 + price);
            dp1 = max(dp1, -price);
        }
        return dp0;
    }
};

代码解释：

• dp0其实表示dp[i-1][0]，即始终记录前一次手里没有股票产生的价值。
• dp1其实表示dp[i-1][1]，即始终记录前一次手里有股票产生的价值。

通过用变量代替数组的方法，成功的将空间复杂度降为了O（1）.
这应该是最为理想的方案了。

---

我最初解决这个问题的时候，采用的是贪心的思想，单纯就这一问题来说，可以很快的得到最佳的答案。

---

0x04.解决问题二（不限交易次数）

1 – 子问题在根问题中情形：

第二个问题，不限制交易的次数，说明k可以为任意值，所以我们就没必要考虑k的大小问题了，可以直接从状态方程中省去。

• 注意：这里的省去，是真正的不去考虑交易次数的影响，而上个问题的省去，是默认k=1的情况。

我们可以快速根据动态规划的思想写出代码。

2 – 运用动态规划思想写出最初代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 0) return 0;
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; 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]);
        }
        return dp[n - 1][0];
    }
};

观察这个问题和上个问题的代码就知道，省去的意义完全不同！

同样的，这里的dp数组也可以优化掉。

3 – 状态压缩，最简代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp0 = 0, dp1 = INT_MIN, temp;
        for (int price : prices) {
            temp = dp0;
            dp0 = max(dp0, dp1 + price);
            dp1 = max(dp1, temp - price);
        }
        return dp0;
    }
};

解释：

• 这里temp存在的意义就是记录上次dp[i-1][0]的值，因为直接使用的话，会是已经改变过的值。

---

这个问题也可以用贪心的思路很快的解决，而且理解起来非常容易。

---

0x05.解决问题三，四（含冷冻期，手续费）

1 – 子问题在根问题中情形：

说白了，问题三，四，在本质上，和问题二是一模一样的，只不过加了一些限制因素，而且这些限制因素并不需要单独作为状态来讨论，只需在处理的时候把这些条件加进去就行了。

• 问题三的冷冻期，就是每次卖出后，要隔一天才能买，但是并没有限制卖的条件，根据这个条件，我们只需要在问题二的基础上，把dp1的计算表达式改为dp1=max(dp1,dp0pre-price)就可以了，其中dp0pre表示前两天手里没有股票的时候的价值，等于实现了卖后隔天买。
• 问题四的手续费就更好处理了，只需要在问题二的基础上，每次买入的时候，额外再减去手续费就行了。
• 其余细节均和问题二相同。

2 – 最终解决代码：

问题三：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp0 = 0, dp1 = INT_MIN, temp, dp0pre = 0;
        for (int price : prices) {
            temp = dp0;
            dp0 = max(dp0, dp1 + price);
            dp1 = max(dp1, dp0pre - price);
            dp0pre = temp;
        }
        return dp0;
    }
};

问题四：

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int dp0 = 0, dp1 = INT_MIN, temp;
        for (int price : prices) {
            temp = dp0;
            dp0 = max(dp0, dp1 + price);
            dp1 = max(dp1, temp - price - fee);
        }
        return dp0;
    }
};

---

这两个问题同样可以采取贪心的思路简单做出

---

0x06.解决问题五（最多交易两次）

1 – 子问题在根问题中情形：

问题五其实就是在k=2的情况，在这个时候，因为k可以取多个值了，所以不能简单的像问题一一样省略k的值，而是需要对k这一状态进行遍历，选择最佳的解。

2 – 运用动态规划思想写出最初代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 0) return 0.;
        int k = 2;
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(2, 0)));
        for (int i = 0; i < n; i++) {
            dp[i][0][0] = 0;
            dp[i][0][1] = INT_MIN;
        }
        for (int i = 0; i < n; i++) {
            for (int j = k; j >= 1; j--) {
                if (i == 0) {
                    dp[0][j][0] = 0;
                    dp[0][j][1] = -prices[i];
                    continue;
                }
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][k][0];
    }
};

这个代码应该不用过多解释，就是根问题的代码形式，不过k为2。
但是直接套用根问题的代码，还是有些复杂，我们可以做一下优化。
说到底，时间复杂度还是O（N）。
优化的思路：

• k为2可以通过穷举出来，可以不使用循环，这一就降低了一个维度。
• 发现dp[i]还是只与dp[i-1]有关，所以，我们可以再次压缩一下状态，将二维变成一维。

3 – 状态压缩，降三维为一维：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp10, dp11, dp20, dp21;
        dp10 = dp20 = 0;
        dp11 = dp21 = INT_MIN;
        for (int price : prices) {
            dp20 = max(dp20, dp21 + price);
            dp21 = max(dp21, dp10 - price);
            dp10 = max(dp10, dp11 + price);
            dp11 = max(dp11, -price);
        }
        return dp20;
    }
};

代码解释：

• dp10其实代表dp[i][1][0]
• dp11其实代表dp[i][1][1]
• dp20其实代表dp[i][2][0]
• dp21其实代表dp[i][2][1]
• 采取这四个变量的目的是穷举k的所有可能
• 压缩的方法与问题二差不多，采取多个变量可以记录前一次的值。

这个方法成功把空间复杂度变为 O（1），应该可以说是最优解绝办法了。

---

这个问题采用其它的方式比较难以理解，最初我是以二维的方法解决这个问题的，
效果还是不佳。

---

0x07.解决问题六（指定交易次数）

这个问题，可以说就是根问题本身了，于是带着根问题的思想，直接尝试了以下，有了一次失败的尝试。。。

失败尝试 – 忽略实际问题的效率

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n <= 0) return 0.;
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(2, 0)));
        for (int i = 0; i < n; i++) {
            dp[i][0][0] = 0;
            dp[i][0][1] = INT_MIN;
        }
        for (int i = 0; i < n; i++) {
            for (int j = k; j >= 1; j--) {
                if (i == 0) {
                    dp[0][j][0] = 0;
                    dp[0][j][1] = -prices[i];
                    continue;
                }
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][k][0];
    }
};

代码是正确的，但在提交的时候，超出了内存的限制，可想而知，这是一个三维的数组，再不济，也是两个二维的，当数据量庞大的时候，容易超出内存的限制。

所以我们要想办法进行降维，第一个降维的思路就是，dp[i]实际还是只和dp[i-1有关，所以这肯定可以降低一个维度。
于是运用这个降维的思想，迅速写出代码。

降低维度的尝试：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n <= 0) return 0.;
        vector<vector<int>> dp(k + 1, vector<int>{0, INT_MIN});
        for (int i = 0; i < n; i++) {
            for (int j = k; j >= 1; j--) {
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = max(dp[j][1], dp[j - 1][0] - prices[i]);
            }
        }
        return dp[k][0];
    }
};

这样成功的降低了一个维度，降低维度的思想整体和问题二差不多，不过这是指定k。

当我再去尝试的时候，发现仍然超出了内存的限制，难道是还要继续降低？？
于是我看了测试的数据，发现k=1000000000，这可是10亿啊，后面肯定没有那么多的数据，所以我应该忽略了k的取值范围。

• 首先，k肯定不能超过n。要不然就没有意义了。但真的只是超过n嘛？
• 一次交易最少需要两天，如果k>=n/2，它已经失去限制的意义了，也就是说，和问题二是一样的了，这就没有必要专门建立一个二维数组了，可以使用问题二的方法来解决。

有了这个思路，我们可以写出详细的代码。

组合解决问题：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n <= 0) return 0.;
        if (k >= n / 2) {
            int dp0 = 0, dp1 = INT_MIN, temp;
            for (int price : prices) {
                temp = dp0;
                dp0 = max(dp0, dp1 + price);
                dp1 = max(dp1, temp - price);
            }
            return dp0;
        }
        vector<vector<int>> dp(k + 1, vector<int>{0, INT_MIN});
        for (int i = 0; i < n; i++) {
            for (int j = k; j >= 1; j--) {
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = max(dp[j][1], dp[j - 1][0] - prices[i]);
            }
        }
        return dp[k][0];
    }
};

最终，这个办法完美的解决了问题。
其实还存在一维的解法，就是用两个一维数组来处理，但是这个方法和我们主要的思想有些偏差，所以就不在这列举了。

细节的处理：

• 在遍历的时候，存在一个内层遍历的方向问题，其实两种方法都是可以的，在这里就不给出证明过程了。
• 有些方法进行了初始化，而有的方法没有，根本原因在于，是否对i层次进行了优化，如果优化了，有些就没有必要了。

至此，所有问题都完美解决了。

0x08.总结 – 深度挖掘动态思想

在分析多个问题时，我们力求找到它们的根问题，然后对根问题就行求解，最后，再根据实际的情况来优化代码，这个过程，就是一个动态的过程。

采用动态规划的思想分析多个问题的基本思路：

• 共性抽取，提取相似的特征
• 异性比较，比较不同的根源
• 问题多变一，将异转变为同
• 找状态，寻找所有可能对结果产生影响的属性
• 找转移方程，择优的过程
• 找初始条件，解决问题的根本
• 遍历所有状态，寻求最优解
• 针对具体的问题，优化没必要的状态
• 进行状态压缩，用最高效的方式解决问题

动态规划思想的本质：

• 动态规划的本质就是一个不断择优的过程，如果是对于 求值问题，那就是一个累加的过程。
• 如何择优成了我们问题的关键。
• 遍历所有可能的情况是择优的基础。

动态的过程如何理解？

• 动态的过程就是静态的不断转变，不断迭代。
• 动就是指所有的状态都在动。
• 规划，就是如何让它们的动，在我们的掌握之中。

一句话概括所有动态规划问题的解法：

遍历所有属性，寻求最优解

至此，本篇博客也已经结束了，该篇博客耗时非常久，旨在通过这一系列的小问题，挖掘出动态规划的本质何核心思想，让以后遇到动态规划问题不再慌张，希望我的文章能对大家有所帮助，仅此而已。

ATFWUS --Writing By 2020–03–18~

!