【动态规划篇】股海擒龙诀：精准狙击股票买卖最佳时机-EW帮帮网

遍历数组，同时维护一个最小价格 min_price 和最大利润 max_profit。

对于每个价格 prices[i]，更新 min_price 为当前最小价格和 prices[i] 中的最小值。

计算当前价格与 min_price 的差值，如果该差值大于 max_profit，更新 max_prof。

②动态规划：

1·状态定义：

定义一个三维数组 dp[i][j][s]，其中 i 表示第 i 天（从 0 到 n-1），j 表示已经进行的交易次数（从 0 到 k），s 表示当前是否持有股票（s = 0 表示不持有，s = 1 表示持有）。

p[i][j][0] 表示在第 i 天，进行了 j 次交易且不持有股票时的最大利润。

dp[i][j][1] 表示在第 i 天，进行了 j 次交易且持有股票时的最大

2·状态转移方程：

1·对于 dp[i][j][0]（不持有股票）：

可能是前一天就不持有股票且不操作，即 dp[i - 1][j][0]。

或者是前一天持有股票，今天卖出，即 dp[i - 1][j][1] + prices[i]。

所以 dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i

2·对于 dp[i][j][1]（持有股票）：

可能是前一天就持有股票且不操作，即 dp[i - 1][j][1]。

或者是前一天不持有股票，今天买入，即 dp[i - 1][j - 1][0] - prices[i]。

所以 dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i

3·初始化：

dp[0][0][0] = 0，表示第一天不进行任何操作时的利润为 0。

dp[0][0][1] = -prices[0]，表示第一天买入股票后的利润为 -prices[0]。

对于其他 j > 0 的情况，将 dp[0][j][0] 和 dp[0][j][1] 初始化为 INT_MIN 或一个足够小的值，因为在第一天不可能完成 j > 0 次交易。

4·最终结果：

最终的最大利润是 dp[n - 1][j][0] 中最大的一个，因为最后一天不持有股票的状态才能得到最大利润。

示例代码（以动态规划为主）：

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n == 0) return 0;
    // dp[i][j][0] 表示在第 i 天，进行了 j 次交易且不持有股票的最大利润
    // dp[i][j][1] 表示在第 i 天，进行了 j 次交易且持有股票的最大利润
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(k+1, INT_MIN));
    dp[0][0][0] = 0;
    dp[0][0][1] = -prices[0];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            // 不持有股票
            dp[i][j][0] = max(dp[i - 1][j][0], (j > 0? dp[i - 1][j - 1][1] + prices[i] : INT_MIN));
            // 持有股票
            dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i]);
        }
    }
    int maxProfit = 0;
    for (int j = 0; j <= k; j++) {
        maxProfit = max(maxProfit, dp[n - 1][j][0]);
    }
    return maxProfit;
}

测试数据：

int main() {
    vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
    cout << maxProfit(prices) << endl;
    return 0;
}

代码分析：

在 maxProfit 函数中，首先初始化 dp 数组。对于 dp[0][0][0] 和 dp[0][0][1] 的初始化表示第一天的状态。

然后通过两层循环，根据状态转移方程更新 dp[i][j][0] 和 dp[i][j][1] 的值。

对于 dp[i][j][0]，考虑不持有股票的两种情况：前一天不持有股票或者今天卖出股票。

对于 dp[i][j][1]，考虑持有股票的两种情况：前一天持有股票或者今天买入股票。

最后遍历 dp[n - 1][j][0] 找出。

5·时间复杂度和空间复杂度分析：

时间复杂度：由于有三层嵌套循环，时间复杂度为 $eq?O%28KN%29$ ，其中 n 是数组的长度，k 是允许的最大交易次数。

空间复杂度：使用了三维数组 dp，空间复杂度为 $eq?O%28KN%29$ 。

3·就上述动态规划以及贪心算法解答总结：

①对于动态规划的解法，要注意状态转移方程的正确性，以及初始化时边界情况的处理，避免出现未初始化或者初始值错误的问题。

在处理边界条件时，如 j = 0 或 i = 0 的情况，需要特别小心，确保状态转移方程的逻辑在这些情况下仍然正确。

①对于贪心算法，它仅适用于简单的买卖股票一次的情况，对于多次交易的情况，需要考虑更复杂的算法，如动态规划。

③总之，根据具体的题目要求和限制条件（如交易次数的限制），可以选择不同的算法来解决买卖股票的最佳时机问题。动态规划是一种通用的方法，但对于简单的情况，贪心算法可以提供更简洁的实现。

那么下面我们就以四道相关的题目展开深入讲解探索吧：

本篇核心的四道示例：

一·买卖股票的最佳时期含冷冻期：

1·1题目：

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

leetcode原题链接： 309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

这里，可以说比较细节的就是有一个限制条件，可以说下面三道题都没有，唯一比较特殊，就是：

1.2状态分析及表示：

所以我们只要注意到这一点，就可以进行状态定义：这里根据题目所给的输入实例的解释可下三个定义状态：即买入，卖出，冷冻期。

那么，也就是这三个状态就够了，但是这里是不是还是有点糊涂，因此我们定义的是时间来到当天，进行当天的操作后，他所处的状态是这三个。 所以我们一定要能理解为什么要是“操作完的状态”。

细节设计问题：还有就是这里其实可以才用多个一维（三个）状态表示出来；其实大差不大；对于时间复杂度也是近似的，因为就算我们用的二维；也只是遍历行完成多个dp同时填充；因此我们这题先用多个二维表示（后序会讲解该如何选择单维还是多维，后面的题有的用到的一维，有的二维，三维等）

 //都是表示当天操作完后的状态：
   //dp[i][0]:买入状态
   //dp[i][1]:卖出状态
   //dp[i][2]:冷冻期状态

1.3状态转移方程：

下面我们通过画状态转移图来分析它的所有可能性（因为肯定是从左到右初始化，因此我们还是往前推理找关系）：

注：这里状态转移图，为了防止漏下情况，因此我们从它自己到自己，然后再看能不能从别的情况到它。

因此我们就得到了状态转移方程：

dp[i][0]=max(dp[i-1][2]-prices[i-1],dp[i-1][0]);
dp[i][1]=max(dp[i-1][0]+prices[i-1],max(dp[i-1][2],dp[i-1][1]));
dp[i][2]=dp[i-1][1];

1.4初始化：

这里虽然我们把它当成二维去用，其实列的那层无需遍历（多个dp状态同时初始化就搞定了）；这里我们dp是从第一行开始遍历（为了应对题目，i就是第一天，故这里要注意与prices数组不是一一对应）因此根据方程可看出都需要知道： $eq?dp%5B0%5D%5B0%5D%2Cdp%5B0%5D%5B1%5D%2Cdp%5B0%5D%5B2%5D$ 。

这里我们可以根据定义推，但是更建议根据如何让我们第一次dp填充是正确的分析（因为它会影响后面每一次填充dp结果）：

我们可以发现：如果第一题直接是卖出状态，以及是冷冻期明显是不可能的；然后我们去试探，可以给它初始化成谁而不影响后面的填充结果呢？其次就是如果是第一天买入肯定是-prices[0]，而第一题处于卖出（无票）收益肯定是0；故我们可以发现如果给后两个都初始化为0 ，而前一个公式是-prices[0]恰好可以第一次正确填充；然后我们使用的vector搞得数组，默认值就是0；因此只用 $eq?dp%5B0%5D%5B0%5D%3D-prices%5B0%5D$ 即可。

1.5确定返回值：

这里发现最后一天肯定是无票才会利益最大；因此它可以是那天刚好卖出（或者前一天之前就卖掉，或者前一天卖掉处理冷冻期）-->也就是我们的 $eq?dp%5Bn%5D%5B1%5D%2Cdp%5Bn%5D%5B2%5D$ 的最大值。

1.6解答代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //都是表示当天操作完后的状态：
          //dp[i][0]:买入状态
          //dp[i][1]:卖出状态
          //dp[i][2]:冷冻期状态
        vector<vector<int>>dp(prices.size()+1,vector<int>(3));
        dp[0][0]=-prices[0];
        for(int i=1;i<=prices.size();i++){
            dp[i][0]=max(dp[i-1][2]-prices[i-1],dp[i-1][0]);//（可以是之前买入，然后处于保持，也可以是当天买入）
            dp[i][1]=max(dp[i-1][0]+prices[i-1],max(dp[i-1][2],dp[i-1][1]));//（可以是之前卖出，但是不是前一天，也可以是当天卖出,或者冷冻期）
            dp[i][2]=dp[i-1][1];//冷冻期前一天必定是卖出（非保持）
        }
        return max(dp[prices.size()][1],dp[prices.size()][2]);

    }
};

最后也是通过了：

二·买卖股票的最佳时机含手续费：

2.1题目：

测试用例：

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

leetcode原题链接： 714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

2.2状态分析及表示：

说白了，这道题其实就是少了上一道题的冷冻期，而多了一个手续费：

其实也是相当于变简单了，因为我们只需要定义两个状态（还是上道题所提及的当天操作完的状态）：即买入状态，卖出状态。

那么下面我们采用两种解法（也就是两个一维状态表示方程以及两个二维的分别来表示）：

但是它其实想法已经做法是一样的，只是呈现给我们的外观是不太一样而已；那么我们就以两个二维状态，一个二维dp为例子分析（后面只需要修改对应二维变一维即可，其他无需太大改变）：


 dp[i][0]:当前天结束时处于买入状态（当天买入或者保持有票）
dp[i][1]:当前天结束时处于售出状态(即当天卖掉或者保持无票)

2.3状态转移方程：

下面我们分析一下该如何对它进行后序的dp填表操作；此时我们依旧可以选择画状态转移图：

2.4初始化：

这里初始化和上道题分析的方法是一样的，这里我们就不做重复分析了：
 dp[0][0]=-prices[0];
 dp[0][1]=0;
 dp[0][2]=0;

2.5确定返回值：

我们如果想让它最后收益最大，故肯定选择最后一天处于售出状态，也就是返回dp[n][1](这里我们还是dp行多开一行为了让每一天与dp下标i对称，因此还要注意prices的下标对应问题了)。

2.6解答代码：

//二维dp(列比较少，直接遍历行就能初始化)：
    // int maxProfit(vector<int>& prices, int fee) {
    //     int n=prices.size();
    //     //dp[i][0]:当前天结束时处于买入状态（当天买入或者保持有票）
    //     //dp[i][1]:当前天结束时处于售出状态(即当天卖掉或者保持无票)
    //     vector<vector<int>>dp(n+1,vector<int>(2));
    //      dp[0][0]=-prices[0];
    //     for(int i=1;i<=n;i++){
    //         dp[i][0]=max(dp[i-1][1]-prices[i-1],dp[i-1][0]);要么当天买入，要么之前就买入了一直处于保持状态
    //         dp[i][1]=max(dp[i-1][0]-fee+prices[i-1],dp[i-1][1]);//要么当天卖出了（注意手续费），要么之前天就卖出了，一直处于保持无股票状态
    //     }
    //     return dp[n][1];
    // }

也必然是通过的：

一维与二维解法的探秘：

但是上面我们不是说了，我们这用的是两个二维状态，一个二维dp；其实也可以用两个一维来同时填充的；是不是又要问了；是不是又要重新画图啥的分析；其实不需要，只是状态等同的用不同状态方程替换，是等同的：

$eq?dp%5Bi%5D%5B0%5D%5CLeftrightarrow%20f%5Bi%5D%3B%20dp%5Bi%5D%5B1%5D%5CLeftrightarrow%20g%5Bi%5D$

然后状态方程表示的时候只需要大概修改一下就好；下面就展示代码：

两个一维dp:
         //f[i]:当前天结束时处于买入状态（当天买入或者保持有票）
         //g[i]:当前天结束时处于售出状态(即当天卖掉或者保持无票)
     int maxProfit(vector<int>& prices, int fee) {
             int n=prices.size();
             vector<int>f(n+1);
             auto g=f;
             f[0]=-prices[0];
             for(int i=1;i<=n;i++){
            f[i]=max(g[i-1]-prices[i-1],f[i-1]);
            g[i]=max(f[i-1]-fee+prices[i-1],g[i-1]);
             }
             return g[n];
     }

当然，这里定义还是看自己，哪个舒服哪个来（时间复杂度还是一样的，只不过，我们可以分析出它有几个状态就用几个一维表示；而上面的二维的列分别表示状态；因此如果状态少就一维，直接给它手动填；如果多的话可以考虑二维；根据自己习惯来就好了）。

三·买卖股票的最佳时机3：

3.1题目：

测试用例：

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

leetcode原题链接：123. 买卖股票的最佳时机 III - 力扣（LeetCode）

3.2状态分析及表示：

首先这道题；对上面两道所涉及的手续费以及冷冻期就全部取消了；但是它加了一个限制条件：

也就是说我们可以完成0~2次交易（因为交易是指买完再卖完才算一次；但是为了后面没有统计重复，我们只需要把卖出就算一次交易即可）

当然了，我们也是只能卖掉手中的股票才能接着买（这四道题都会遵循这个条件）。

因此还是分两种状态：

买入状态（可能是当天买入也可以是之前就买入处于保持有票状态）。

卖出状态（可能是当天卖出也可以是之前就卖出处于保持无票状态）。

但是要注意：这里还要有交易次数的限制；因此我们搞一个二维状态；也把它表示出来（有的题解它是对次数判断；这里我们直接让它自己填充好也就是遍历到最大次数（因为第四题就这个方法是通用的模子直接照搬就好））。

 f[i][j]:表示到了i天此次操作结束后是进行了j次交易且手中有股票的最大钱
 g[i][j]:表示到了i天此次操作结束后是进行了j次交易且手中无股票的最大钱

3.3状态转移方程：

下面还是根据状态转移图分析（防止落下情况）：

因此就可以得到下面的状态方程表示：

但是这样就一定对吗？肯定不是；下面我们就在初始化环节展开分析把。

3.4初始化：

这里我们为了后序填表是正确的进而得到答案是正确的，因此初始化也是至为重要的；而首先我们可以的根据f的表达式得到：

但是这样就完了吗？其实我们还没有考虑其他项，也就是整个vector创建的时候默认初始化谁；我们可以发现虽然这道题次数最多是2次；而后面就会出现k次；因此像这样：第0天不可能有交易；

第一题不可能有两次交易： $eq?f%5B0%5D%5B1%5D%3Bf%5B1%5D%5B2%5D%3B$ 这样相当于无关项（也就是不可能存在的情况）；因为第一题如果有票说明此刻收益必然是负数；因此我们最好都初始化为负无穷；防止其他无关项的干扰即可。

注：这里有个小技巧（vector初始化）：有min考虑最大值；有max考虑最小值。

但是直接初始化成INT_MIN就行了吗；但是这里还是不建议的，万一有天还需要卖；而此时收益还未初始化，但是却会和前面填的值（正数）取max;这里最小值还会减小；这就不行了；因此我们设置成-0x3f3f3f3f(上面最小值的一般，也能防止相减的时候越界变成正数的行为发生) 。

其实之前篇我们也介绍了区别：【动态规划篇】步步带你深入解答成功AC最优包含问题（通俗易懂版）-CSDN博客

这里我们再说一遍：

INT_MIN，INT_MAX与0x3f3f3f3f,-0x3f3f3f3f适配：

`①INT_MAX`和`INT_MIN：`

定义和用途：

在 C/C++ 语言中，INT_MAX和INT_MIN是在<limits.h>头文件中定义的，用于表示int类型所能表示的最大值和最小值。例如，在 32 位有符号整数系统中，INT_MAX通常是 2147483647（ $eq?2%5E%7B31%7D-1$ ），INT_MIN是 - 2147483648（ $eq?2%5E%7B-31%7D$ ）。它们是语言提供的标准方式来处理整数类型的边界值，主要用于边界检查、防止整数溢出等情况。

在算法中的应用场景：

当需要确定一个整数变量所能达到的最大或最小边界时，INT_MAX和INT_MIN可以派上用场。比如在一些图算法中，初始化最短路径长度。如果用 Dijkstra 算法求单源最短路径，对于尚未访问的节点，可以将其距离初始化为INT_MAX，表示初始状态下从源节点到这些节点的距离是无穷大。

②0x3f3f3f3f:

定义和性质：

0x3f3f3f3f是一个十六进制数，它对应的十进制数是 1061109567。这个数有几个特殊的性质，它是一个足够大的数，同时它的两倍不会溢出int类型（在大多数常见的编译器环境下）。而且这个数的每个字节都是0x3f，在内存中看起来比较整齐。

在算法中的应用场景与优势(这也就是我们本篇的原因了):

->初始化数组：在许多算法中，如初始化动态规划数组或者图的邻接矩阵等。以动态规划为例，当计算最长公共子序列等问题时，可能需要初始化一个二维数组来存储中间状态。使用0x3f3f3f3f作为初始值可以避免一些边界问题，并且在后续的状态更新中，如果想要判断某个状态是否已经被更新过，可以通过比较是否等于0x3f3f3f3f来确定。相比之下，INT_MAX在一些运算中可能会因为溢出等问题导致错误。

->表示无穷大替代方案：在某些情况下，它可以作为INT_MAX的替代来表示 “无穷大” 的概念。例如在一些自定义的贪心算法或者搜索算法中，当需要一个很大的数来初始化某个代价或者距离等变量时，0x3f3f3f3f比INT_MAX更具优势。因为INT_MAX加上一个正数可能会溢出，而0x3f3f3f3f在合理的运算范围内不太容易出现这种问题。同时，在进行比较和更新操作时，0x3f3f3f3f也能够很好地发挥作用，帮助算法正确地选择最优的路径或者状态。

其次就是我们初始化（这里仅仅交易限制最大是2；但是后面如果是多次呢；因此这个数组我们不能手动填写；直接让第二次循环从0开始就好，利用循环填充）：

那么这就会导致越界了：

可根据题意得知：第一天如果无票；之前肯定无票故没有交易j=0；即选择前者；无需考虑后者即可：加个判断即可。

 g[i][j]=j>=1?max(g[i-1][j],f[i-1][j-1]+prices[i-1]):g[i-1][j];

3.5确定返回值：

这里我们要明白还是最后一次无票状态才可能利润最大故选择g的方程；其次就是最后一天，我们不知道它进行了多少次交易，故只需要遍历g的最后一行求max即可。

int ret=0;
   for(auto a:g[n]) ret=max(ret,a);//这里由于最后一定是卖掉了也就是g；遍历0-j次交易的最大值即可
     return ret;

3.6解答代码：

  //f[i][j]:表示到了i天此次操作结束后是进行了j次交易且手中有股票的最大钱
      //g[i][j]:表示到了i天此次操作结束后是进行了j次交易且手中无股票的最大钱
     //两个二维状态表示：
    // int maxProfit(vector<int>& prices) {
    //     int n=prices.size();
    //     vector<vector<int>>f(n+1,vector<int>(3,-0x3f3f3f3f));//把无用项初始化算法中的可认为最小值（因为如果是INT_MIN，INT_MAX这样可能会超限；这里
    //     //对0x3f3f3f3f这样使它的一般加一般数不会越界）
    //     auto g=f;
    //     f[0][0]=-prices[0];//为了初始化f[1][0];
    //     g[0][0]=0;//为了初始化g[1][0]
    //     for(int i=1;i<=n;i++){
    //         for(int j=0;j<=2;j++){
    //             f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i-1]);可能上一天也是有股票并未买入，也可能是i这天买入（即i-1这天无股票）
    //             //这里我们不能从1开始遍历j；因为后面否则每个[0][j]我们都要初始化麻烦（因为我们只有第一个00有用，其他都是无关项），
    //             //这里根据防止空访问只需做个判断即可
    //             g[i][j]=j>=1?max(g[i-1][j],f[i-1][j-1]+prices[i-1]):g[i-1][j];要么前一天也是没股票状态，要么当天就把股票卖了
    //         }
    //     }
    //     int ret=0;
    //     for(auto a:g[n]) ret=max(ret,a);//这里由于最后一定是卖掉了也就是g；遍历0-j次交易的最大值即可
    //     return ret;
    // }

最后也必然通过：

二维解法向三维的过渡：

当然了这道题我们使用两个二维去表示的；也可以定义两个三维状态然后用一个三维dp表示：


 //定义两个三维dp状态（实际遍历填表还是按照二维o(N^2）因为这里两个dp同时填直接第三维是常数级别)：
 //dp[i][j][0]:表示到了i天此次操作结束后是进行了j次交易且手中有股票的最大
 //dp[i][j][1]:表示到了i天此次操作结束后是进行了j次交易且手中无股票的最大钱

而后面我们只需要两层for就可以ok，这里需要改的地方：就是vector的初始化，0 0的初始化；以及遍历范围；查询最大值；这些其实也是和上面的二维的稍微改变一下就好：

int maxProfit(vector<int>& prices) {
       int n=prices.size();
        vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(3,vector<int>(2,-0x3f3f3f3f)));
        dp[0][0][0]=-prices[0];
        dp[0][0][1]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=2;j++){
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]-prices[i-1]);
                dp[i][j][1]=j>=1?max(dp[i-1][j][1],dp[i-1][j-1][0]+prices[i-1]):dp[i-1][j][1];
            }
        }
        int ret=0;
        for(int k=0;k<=2;k++)ret=max(ret,dp[n][k][1]);
        return ret;
    
    }

当然代码一定是能跑同的啦！

四·买卖股票的最佳时机4：

题目：

测试用例：

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

leetcode原题链接：188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

这里博主就偷个懒啦：

其实这道题就是上面的最大两次交易的最大利润的值把两次改成k次即可了，之所以博主上面的题的解法不是直接判断（因为2次也不是很多，为了下面的k次做铺垫）因此我们只需要把关于2的地方对应改成k就好啦（这里同样二维与三维都是可以，这里博主就只展示二维的表示了）：

class Solution {
public:
    //j<=2
      //f[i][j]:表示到了i天此次操作结束后是进行了j次交易且手中有股票的最大钱
      //g[i][j]:表示到了i天此次操作结束后是进行了j次交易且手中无股票的最大钱

    int maxProfit(int k, vector<int>& prices) {
         int n=prices.size();
        vector<vector<int>>f(n+1,vector<int>(k+1,-0x3f3f3f3f));
        auto g=f;
        f[0][0]=-prices[0];
        g[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i-1]);
                g[i][j]=j>=1?max(g[i-1][j],f[i-1][j-1]+prices[i-1]):g[i-1][j];
            }
        }
        int ret=0;
        for(auto a:g[n]) ret=max(ret,a);
        return ret;
    }
};

也是通过：

五·就买卖股票最佳时机个人总结：

1·就是我们定义状态的时候可以选择单维也可以是多维：那要选择哪个呢？如果我们需要的状态比较多；手动一个个给它填充麻烦；因此就设置成多维；否则单位维即可（其实一般时间复杂度是近似一样的）。

2·就是我们去得到状态方程：这里如果状态较多；为了防止落下某种状态：可以考虑话画状态转移图来完成（先自己到自己后别人到自己）。

3·就是初始化，此时就要我们结合它的实际意义（我们是如何定义的这种状态）以及为了保证后面填充dp的时候用到它，它是对的（它的正确性）。

以上就是博主对本篇探讨问题与大家的分享以及博主个人总结技巧等；希望对大家有帮助 !!!

【动态规划篇】股海擒龙诀：精准狙击股票买卖最佳时机

本篇简介：

浅入买卖股票最佳时机 ：

1·问题描述：

2·解题思路：

①贪心法：

②动态规划：

3·就上述动态规划以及贪心算法解答总结：

本篇核心的四道示例：

一·买卖股票的最佳时期含冷冻期：

1·1题目：

1.2状态分析及表示：

1.3状态转移方程：

1.4初始化：

1.5确定返回值：

1.6解答代码：

二·买卖股票的最佳时机含手续费：

2.1题目：

2.2状态分析及表示：

2.3状态转移方程：

2.4初始化：

2.5确定返回值：

2.6解答代码：

一维与二维解法的探秘：

三·买卖股票的最佳时机3：

3.1题目：

3.2状态分析及表示：

3.3状态转移方程：

3.4初始化：

INT_MIN，INT_MAX与0x3f3f3f3f,-0x3f3f3f3f适配：

①INT_MAX和INT_MIN：

②0x3f3f3f3f:

3.5确定返回值：

3.6解答代码：

二维解法向三维的过渡：

四·买卖股票的最佳时机4：

五·就买卖股票最佳时机个人总结：

网站公告

今日签到

热门文章

最新发布

浅入买卖股票最佳时机：

`①INT_MAX`和`INT_MIN：`