买卖股票相关的动态规划题目

文章目录

• 1.买卖股票的最佳时机含冷冻期
• 2.买卖股票的最佳时期含⼿续费
• 3.买卖股票的最佳时机III
• 4.买卖股票的最佳时机IV

  ---

  1.最佳买卖股票时机含冷冻期

  力扣链接：力扣

  给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​

  设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

  注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

  

   首先我们分析一下题目，题目中的要点是卖出股票后第二天不能买入，并且每次买新的股票前都要出售掉原先的股票，有了这个限制条件，我们就很容易分析出这道题是多状态的dp。

  1.状态表示

  当我们以dp[i]表示第i天结束的最大利润时，我们发现无法写出状态转移方程，因为要求第i天的最大利润，我们要看第i天是否是冷冻期或者是否手中无股票或者手中有股票，所以我们将有三种状态表示：

  f[i]表示第i天手中有股票的最大利润

  g[i]表示第i天手中没有股票的最大利润

  s[i]表示第i天处于冷冻期的最大利润

  2.状态转移方程

  

  首先我们要分析每种状态，比如我们第i天持有股票，那么从哪一个状态可以到有股票的状态呢？当前一天也就是i-1天就有股票的时候，我们什么也不干到了第i天还是处于有股票的状态。当前一天是没有股票的状态，那么我们在前一天买股票到了第i天就处于有股票状态。

  所以f[i] = max(f[i-1],g[i-1] - p[i])

  接下来我们分析没有股票的状态，首先如果前一天就没有股票，那么什么也不干到了第i天还是处于没有股票的状态。如果前一天是冷冻期，那么什么也不干到了第i天就自动处于没有股票状态（因为冷冻期一定是卖出股票了，一旦卖出手中就没有股票了）。

  所以 g[i] = max(g[i-1],s[i-1])

  接下来我们分析冷冻期，冷冻期一定是卖出股票才会有的，所以前一天是有股票状态，然后将股票卖出，第i天就是冷冻期。

  所以s[i] = f[i-1] + p[i];

  3.初始化

  从状态转移方程我们可以看到每次需要前一天的利润，那么只有第1天会越界，所以我们直接初始化三个表的第一天，第一天要有股票那么就得买入，买入利润就从0变成负数，所以f[0] = -p[0]

  第一天没有股票那么什么也不干就可以，所以g[0] = 0

  第一天就处于冷冻期那么利润一定为0 所以s[0] = 0

  4.填表

  从左向右，三个表一起填

  5.返回值

  返回三个表的最后一天的最大值。

  class Solution {
  public:
      int maxProfit(vector& prices) {
          int n = prices.size();
          vector f(n,0),g(n,0),s(n,0);
          f[0] = -prices[0];
          for (int i = 1;i 
  当然我们也可以将代码优化一下，最后一天如果手里还有股票没卖出去，那么这一天的利润一定是比无股票状态和冷冻期状态低的，所以我们只需要返回卖出股票状态的最大值即可：
   
   
  当然，我们上面用三个一维数组表示状态是比较冗余的，我们可以用二维数组来表示，代码如下：
   
  class Solution {
  public:
      int maxProfit(vector& prices) {
          int n = prices.size();
          vector> dp(n,vector(3,0));
          dp[0][0] = -prices[0];
          for (int i = 1;i 
   上面我们是以dp[i][0]表示有股票状态，dp[i][1]表示无股票状态，dp[i][2]表示冷冻期。
   
   
  2.买卖股票的最佳时机含手续费
   
  力扣链接：力扣
   
  给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
   
  你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
   
  返回获得利润的最大值。
   
  注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
   
   
   这道题是我们做的第一道题的变种，我们先来分析一下这道题中的细节：
   
  首先这次没有冷冻期了可以随便交易，但是每笔交易需要付手续费，这里要注意了，一笔交易是指有股票然后卖出，可以理解为只有卖出的时候需要交手续费。并且这道题和第一题一样，都是只有卖出原先的股票才能购买新的股票。
   
  1.状态表示
   
  我们根据上一题的经验，直接用f[i]表示第i天手中有股票的最大利润，用g[i]表示第i天手中没有股票的最大利润。
   
  2.状态转移方程
   
   
   因为此题只有两种状态，所以我们直接分析：
   
  当前一天也就是i-1天就有股票的时候，我们什么也不干到了第i天还是处于有股票的状态。当前一天是没有股票的状态，那么我们在前一天买股票到了第i天就处于有股票状态。
   
  所以f[i] = max(f[i-1],g[i-1]-p[i])
   
  首先如果前一天就没有股票，那么什么也不干到了第i天还是处于没有股票的状态。如果前一天有股票，那么我们卖出股票就变成了没有股票状态。
   
  所以g[i] = max(g[i-1],f[i-1] + p[i] -fee)   //注意卖出股票需要支付手续费
   
  3.初始化
   
  只有第一天会越界，所以我们直接初始化两个表的第一天的最大利润：
   
  第一天要有股票那么就得买入，买入利润就从0变成负数，所以f[0] = -p[0]
   
  第一天没有股票那么什么也不干就可以，所以g[0] = 0
   
  4.填表
   
  从左向右，两个表一起填
   
  5.返回值
   
  返回最后一天是卖出状态的最大利润即可。（因为最后一天手中没股票一定比手中有股票的利润大）
   
  class Solution {
  public:
      int maxProfit(vector& prices, int fee) {
         int n = prices.size();
         vector f(n,0),g(n,0);
         f[0] = -prices[0];
         for (int i = 1;i 
   
  3.买卖股票的最佳时机 III
   
  力扣链接：力扣
   
  给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
   
  设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
   
  注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
   
   
   这道题和我们上一题基本一样，就是多了一个最多完成两笔交易的限制，下面我们直接开始分析。
   
  1.状态表示
   
  我们根据前两道题的经验，先以f[i]表示第i天手中有股票的最大利润，g[i]表示第i天手中没有股票的最大利润，但是我们发现这样的状态表示无法限制最多完成两笔交易，所以我们直接多加一个状态就可以了，用f[i][0]代表第i天进行了0笔交易手中有股票的最大利润，f[i][1]代表第i天进行了1笔交易手中有股票的最大利润，f[i][2]代表第i天进行了2笔交易手中有股票的最大利润，g表同理。
   
  所以f[i][j]代表第i天交易了j次，处于有股票状态。
   
  g[i][j]代表第i天交易了j次，处于没有股票的状态。
   
  2.状态转移方程
   
   
   
  当前一天也就是i-1天就有股票的时候，我们什么也不干到了第i天还是处于有股票的状态。当前一天是没有股票的状态，那么我们在前一天买股票到了第i天就处于有股票状态。
   
  所以f[i][j] = max(f[i-1][j],g[i-1][j]-p[i])  注意：前一天处于有股票的状态，那么什么也不干第i天还是处于有股票的状态，所以我们的交易次数是不变的，还是j次。如果前一天是没有股票状态，那么买了股票就到了有股票状态，但是我们要注意只有卖出股票才算一次交易，所以这里还是j次交易没有改变。
   
  首先如果前一天就没有股票，那么什么也不干到了第i天还是处于没有股票的状态，并且交易次数不发生改变。如果前一天有股票，那么我们卖出股票就变成了没有股票状态，但是卖出股票就会增加一次交易，而我们要求的实际上是第i天的交易，也就是说增加完一次交易后交易次数才变成了j，那么在求前一天的有股票的利润时应该按照j-1的交易次数（因为前一天有股票，第i天卖出变成没有股票状态，一旦卖出交易次数+1，默认第i天是j次交易的话，那么第i-1天就是j-1次交易）
   
  所以g[i] = max(g[i-1][j],f[i-1][j-1]+p[i])
   
  3.初始化
   
  通过状态转移方程可以发现，每次要求前一天相应交易次数的最大值，而为了原来表中的数据不影响取最大值，就将表中每个数据初始化为整形的最小值，但是由于有-p[i]的存在，会使整形的最小值溢出，所以我们只取一半整形的最小值就好了。
   
  第一天要有股票并且不交易（也就是不卖出）那么利润就从0变成负数，所以f[0][0] = -p[0]
   
  第一天没有股票并且交易次数为0，那么什么也不干就可以，所以g[0][0] = 0
   
  4.填表
   
  每一行从上往下，每一列从左向右，两个表一起填
   
  5.返回值
   
  返回最后一天是卖出状态的并且交易是0,1,2三种中的最大利润即可。（因为题目只限制不超过2笔交易，但是不能保证交易次数多一定利润大，当只有一天的股票的时候，不交易是利润最大的）
   
  class Solution {
  public:
      int maxProfit(vector& prices) {
          int n = prices.size();
          const int Min = -0x3f3f3f3f;
          vector> f(n,vector(3,Min));
          auto g = f;
          f[0][0] = -prices[0];
          g[0][0] = 0;
          for (int i = 1;i=1)
                  {
                      g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);
                  }
              }
          }
          int ret = g[n-1][0];
          for (int i = 1;i<3;i++)
          {
              if (ret 
  需要注意的是，我们的f[i-1][j-1]这种情况只有在j>=1的时候才不会越界，所以当j = 0的时候我们只需要让g[i][j] = g[i-1][j]
   
   
  4.买卖股票的最佳时机 IV
   
  力扣链接：力扣
   
  给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。
   
  设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
   
  注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
   
   
   其实大家不难发现，这道题和我们上一题的区别只有交易的最大限制，而我们也只需要将上一题的两笔交易修改为k笔交易即可。
   
  1.状态表示
   
  f[i][j]代表第i天交易了j次，处于有股票状态。
   
  g[i][j]代表第i天交易了j次，处于没有股票的状态。
   
  2.状态转移方程
   
  当前一天也就是i-1天就有股票的时候，我们什么也不干到了第i天还是处于有股票的状态。当前一天是没有股票的状态，那么我们在前一天买股票到了第i天就处于有股票状态。
   
  所以f[i][j] = max(f[i-1][j],g[i-1][j]-p[i])  注意：前一天处于有股票的状态，那么什么也不干第i天还是处于有股票的状态，所以我们的交易次数是不变的，还是j次。如果前一天是没有股票状态，那么买了股票就到了有股票状态，但是我们要注意只有卖出股票才算一次交易，所以这里还是j次交易没有改变。
   
  首先如果前一天就没有股票，那么什么也不干到了第i天还是处于没有股票的状态，并且交易次数不发生改变。如果前一天有股票，那么我们卖出股票就变成了没有股票状态，但是卖出股票就会增加一次交易，而我们要求的实际上是第i天的交易，也就是说增加完一次交易后交易次数才变成了j，那么在求前一天的有股票的利润时应该按照j-1的交易次数（因为前一天有股票，第i天卖出变成没有股票状态，一旦卖出交易次数+1，默认第i天是j次交易的话，那么第i-1天就是j-1次交易）
   
  所以g[i] = max(g[i-1][j],f[i-1][j-1]+p[i])
   
  3.初始化
   
  通过状态转移方程可以发现，每次要求前一天相应交易次数的最大值，而为了原来表中的数据不影响取最大值，就将表中每个数据初始化为整形的最小值，但是由于有-p[i]的存在，会使整形的最小值溢出，所以我们只取一半整形的最小值就好了。
   
  第一天要有股票并且不交易（也就是不卖出）那么利润就从0变成负数，所以f[0][0] = -p[0]
   
  第一天没有股票并且交易次数为0，那么什么也不干就可以，所以g[0][0] = 0
   
  4.填表
   
  每一行从上往下，每一列从左向右，两个表一起填
   
  5.返回值
   
  返回最后一天是卖出状态的并且交易是K种中的最大利润即可。（因为题目只限制不超过K笔交易，但是不能保证交易次数多一定利润大，当只有一天的股票的时候，不交易是利润最大的）
   
  class Solution {
  public:
      int maxProfit(int k, vector& prices) {
          int n = prices.size();
          const int Min = -0x3f3f3f3f;
          vector> f(n,vector(k+1,Min));
          auto g = f;
          f[0][0] = -prices[0];
          g[0][0] = 0;
          for (int i = 1;i=1)
                  {
                      g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);
                  }
              }
          }
          int ret = g[n-1][0];
          for (int i = 1;i 
  注意：我们上一题两笔交易的时候，要开3个位置，这是因为还要0笔交易也就是不交易的情况，所以这道题给出K笔交易的时候我们还要多加1用来表示第0笔交易。
   
   50个市场营销经典案例  手机网站建设app  专业网站优化  成都正规制作网站公司  如何自助建站  网络科技公司排名