状态机动态规划之股票问题总结

在前面的三篇股票问题的文章当中我们一共介绍了6道关于股票相关的算法题，这些算法题的一个集中的特点就是状态比较多，需要我们去仔细分析状态之间的转换，而这种状态之间的转换特变像状态机，因此这种动态规划也被称作状态机动态规划。

如果需要仔细的去分析上面思维导图当中的各个问题，可以参考下面的文章：

本篇文章就是对上面6个问题进行汇总方便大家查阅，如果大家想仔细分析这几个问题还是上面三篇文章更合适，内容更加详细，如果你想快速了解状态机动态规划，那么这篇文章的状态转移分析应该能够帮助你。

在本文谈到的6个问题都是动态规划的问题，因此你可以需要熟悉一下动态规划的套路，在求解动态规划问题的时候通常的步骤有以下几个：

• 寻找能够表示状态的数组dp，即我们需要寻找dp的含义，分析需要用几纬数组表示具体的状态。
• 通过分析问题，寻找动态转移公式。
• 初始化状态数组。
• 通过分析动态转移方程，确定数组的遍历顺序。

买卖股票的最佳时机I

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

状态表示数组

在这个问题当中我们用一个二维数组去表示我们的状态，在这个问题当中主要有两个状态，一个是手上有股票，另一是手上没有股票：

• dp[i][0]表示在第i天手上没有股票能够获得的最大的收益，比如我们在第一天的没有股票的收益为0元。

• dp[i][1]表示在第i天手上存在股票能够获得的最大的收益，比如我们在第一天买入股票之后收益为-prices[0]。

那么我们最后的答案是dp[N][0]，这个表示在最后一天，我们的手中不存在股票，即我们将股票卖出去能够获取的最大的收益。

状态转移方程

现在我们来分析一下如何进行状态的转移：

• dp[i][0]的状态如何从第i-1的状态转移过来：

  • 如果第i-1个状态是手中不存在股票，即dp[i-1][0]，那么第i个状态也没有股票，那么直接是dp[i][0] = dp[i - 1][0]，因为没有进行交易。
  • 如果第i-1个状态手中存在股票，即dp[i-1][1]，那么如果想在第i个状态没有股票，那么就需要将股票卖出，那么收益就为dp[i-1][1] +prices[i]，即dp[i][0] = dp[i-1][1] +prices[i]。
  • 综合上面的两种转移方式可以得到下面的转移方程：
  dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i])

• dp[i][1]的状态如何进行转移：

  • 如果第i-1个状态是手中不存在股票，即dp[i-1][0]，而第i个状态有股票，那么dp[i][0] = -prices[i]，因为买入股票，而且只能够买入一次，因此直接等于-prices[i]即可，注意这里不能是dp[i - 1][0] - prices[i]，因为在dp[i-][0]当中可能存在先买入再卖出的情况，而题干要求只能买入卖出一次。
  • 如果第i-1个状态手中存在股票，即dp[i-1][1]，而第i个状态有股票，因此不需要进行交易，即dp[i][1]=dp[i - 1][1]。
  • 综合上面的两种转移方式可以得到下面的转移方程：
  dp[i][1]=max(dp[i−1][1],−prices[i]);

参考代码如下：

class Solution { public int maxProfit(int[] prices) { int[][] dp = new int[prices.length][2]; // 初始化数组 dp[0][0] 默认等于0 不用 // 显示初始化 dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); } return dp[prices.length - 1][0]; }}

进行数组空间优化

class Solution { public int maxProfit(int[] prices) { int[][] dp = new int[2][2]; dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; i++) { dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i]); dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], -prices[i]); } return dp[(prices.length - 1) & 1][0]; }}

买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回你能获得的最大 利润。

状态表示数组

在这个问题当中我们用一个二维数组去表示我们的状态，在这个问题当中主要有两个状态，一个是手上有股票，另一是手上没有股票：

• dp[i][0]表示在第i天手上没有股票能够获得的最大的收益，比如我们在第一天的没有股票的收益为0元。

• dp[i][1]表示在第i天手上存在股票能够获得的最大的收益，比如我们在第一天买入股票之后收益为-prices[0]。

那么我们最后的答案是dp[N][0]，这个表示在最后一天，我们的手中不存在股票，即我们将股票卖出去能够获取的最大的收益。

状态转移方程

现在我们来分析一下如何进行状态的转移：

• dp[i][0]的状态如何从第i-1的状态转移过来：

  • 如果第i-1个状态是手中不存在股票，即dp[i-1][0]，那么第i个状态也没有股票，那么直接是dp[i][0] = dp[i - 1][0]，因为没有进行交易。
  • 如果第i-1个状态手中存在股票，即dp[i-1][1]，那么如果想在第i个状态没有股票，那么就需要将股票卖出，那么收益就为dp[i-1][1] +prices[i]，即dp[i][0] = dp[i-1][1] +prices[i]。
  • 综合上面的两种转移方式可以得到下面的转移方程：
  dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i])

• dp[i][1]的状态如何进行转移：

  • 如果第i-1个状态是手中不存在股票，即dp[i-1][0]，而第i个状态有股票，这道题目和上一道题目只有这个地方是不一致的，在上一道题当中dp[i][0] = -prices[i]，这是因为只能够买入股票一次，具体原因是在dp[i - 1][0]当中可以存在股票买入，而且已经卖出这种情况，而第一题只能买入卖出一次，而在这道题目当中，能够买卖股票多次，因此dp[i][0] = dp[i - 1][0] - prices[i]。
  • 如果第i-1个状态手中存在股票，即dp[i-1][1]，而第i个状态有股票，因此不需要进行交易，即dp[i][1]=dp[i - 1][1]。
  • 综合上面的两种转移方式可以得到下面的转移方程：
  dp[i][1]=max(dp[i−1][1],dp[i−1][0]−prices[i]);

• 综合上面的两个状态：

参考代码如下：

class Solution { public int maxProfit(int[] prices) { int[][] dp = new int[2][2]; dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; i++) { dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i]); dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][0] - prices[i]); } return dp[(prices.length - 1) & 1][0]; }}

买卖股票的最佳时机 III

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

状态表示数组

在这道题目当中我们也是二维数组进行状态的表示，二维数组为dp[N][5]，5表示我们有5个状态，dp[N][i]表示第N天的第i个状态能够多大的收益！（为了方便下面介绍，假设一天有一个股票，dp[N][]表示第N天的状态，对应第N个股票的状态）

• dp[N][0]，表示第N天一次买入和卖出的操作都没有过，那么dp[N][0] = dp[N - 1][0]，跟前一天的状态一样，都没有进行股票的买入和卖出，其实也可以直接令dp[N][0] = 0，因为没有进行操作我们的收益肯定等于0。
• dp[N][1]，表示第N天已经进行过第一次买入，这个买入可以是在第N天进行买入，也可以在前面N-1天买入，然后在第N天保持状态。
  • 如果第N天刚刚进行买入，那么我们的收益就是从前一天一次买入和卖出都没有操作转移过来的，那么就有dp[N][0] - prices[i]，因为根据上面的分析dp[N][0] = 0，那么直接让dp[N][1] = -prices[i]即可。
  • 如果在前N-1天已经进行了买入，那么在第N天就不行操作，即在第N天收入为0，即dp[N][1] = dp[N - 1][1]。
• dp[N][2]，表示第N天已经进行过第一次卖出，这个状态可以是在第N天进行卖出，也可以是在前面N-1天已经卖出，然后在第N天保持状态
  • 如果在第N天进行第一次卖出那么我们在第N天的收益就等于prices[i]，再加上前N-1天买入一次的收益，即dp[N][2] = dp[N - 1][1] + prices[i]。
  • 如果前N-1天已经卖出，那么直接保持状态即可，我们在第N天的收益就为0，那么dp[N][2] = dp[N - 1][2]。
• dp[N][3]，表示第N天已经进行过第二次买入，这个状态可以是在第N天进行买入，也可以是在前面N-1天买入，然后在第N天保持状态。
  • 如果在第N天进行第二次买入那么我们在第N天的收益就等于-prices[i]，再加上前N-1天买入卖出一次的收益，即dp[N][3] = dp[N - 1][2] - prices[i]。
  • 如果前N-1天已经有了第二次买入的操作，那么直接保持状态即可，我们在第N天的收益就为0，那么dp[N][3] = dp[N - 1][3]。
• dp[N][4]，表示第N天已经进行过第二次卖出，这个状态可以是在第N天进行买入，也可以是在前面N-1天卖出，然后在第N天保持状态。
  • 如果是在第N天卖出，那么在第N天的收益为prices[i]，再加上前N-1天买入两次卖出一次的收益dp[N][3]，那么dp[N][4] = dp[N - 1][3] + prices[i]。
  • 如果是前N-1天已经买入卖出两次了，那么直接保持前一天的状态即可，即dp[N][4] = dp[N-1][4]。

状态转移方程

假如可以买卖股票的天数一共有N天，那么我们最终需要求出来的结果是dp[N][4]，表示第N天已经买入卖出2次，将两次使用的机会都是用完了，为什么我们最终的结果是dp[N][4]呢？这你可能疑惑万一我买入一次卖出一次能够得到的收益最大呢？我们是允许在同一天多次买入和卖出股票的，而在同一天买入和卖出股票收益为0，所以不影响最后的结果，因此买入卖出一次最终也可以转移到买入卖出两次（其中一次在同一天买入和卖出即可，我们在对数组进行初始化的时候就需要进行多次买入和卖出（可以看下文当中对数组初始化的分析）），因此我们最终需要返回的结果就是dp[N][4]。

而根据上面的分析我们知道，从上图可以看出转移到dp[N][4]这个状态一共有两种方式，我们应该选择转移之后两者方式得到的价值比较大的那个，即dp[N][4] = max(dp[N - 1][4], dp[N - 1][3] + prices[i]);，而dp[N - 1][4]的转移又有两种方式我们也应该选择其中较大的，dp[N - 1][3]也有两种转移方式，因此其也应该选择两者当中比较大的那个值，即dp[N][3] = max(dp[N - 1][3], dp[N - 1][2] - prices[N]);，同理我们可以得到其他状态的转移方程，每个数据都是需要选择转移之后价值最大的那个，最终我们的状态转移方程如下：

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

代码如下：

class Solution { public int maxProfit(int[] prices) { int[][] dp = new int[prices.length][5]; // dp[i][0] 表示一次买入和卖出都没有 // dp[i][1] 表示第一次买入 // dp[i][2] 表示第一次卖出 // dp[i][3] 表示第二次买入 // dp[i][4] 表示第二次卖出 dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for (int i = 1; i < prices.length; i++) { dp[i][0] = dp[i - 1][0]; dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]); dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]); dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]); } return dp[prices.length - 1][4]; // 注意数据之前传递依赖的关系 // 因为要求 dp[N][4] 当中 // 最大的值 因此需要求解 dp[N - 1][4] 和 dp[i - 1][3] 的最大值 // ...... }}

买卖股票的最佳时机 IV

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

状态表示数组和动态转移方程

这个问题上面一个问题其实差不多，只不过上面的问题是最多完成两笔交易，而在这个问题当中是最多可以完成k笔交易，这个问题相当于上面问题的推广，我们再来分析一下上一道题目的动态转移公式：

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

上面的公式用一个公式表示就是：

现在我们将这个问题进行推广：

• • dp[i][0] 表示一次买入和卖出都没有。
  • dp[i][2 * k - 1] 表示第 k 次买入。
    • 根据上文的分析，这个地方类似，有两种状态可以转换成第k次买入这个状态。
      • 如果前i-1天已经有k次买入了，则保持前面的状态就行，即dp[i][2 * k - 1] = dp[i - 1][2 * k - 1]。
      • 如果前i-1天已经有k-1次买入和卖出了，那么就需要进行买入，即dp[i][2 * k - 1] = dp[i - 1][2 * k - 2]- prices[i] 。
  • dp[i][2 * k] 表示第 k 次卖出。
    • 同样的，也有两个状态可以转换成这个状态。
      • 如果前i-1天已经有k次卖出了，则保持前面的状态就行，即dp[i][2 * k] = dp[i - 1][2 * k]。
      • 如果前i-1天已经有k次买入，那么就需要进行买入，即dp[i][2 * k] = dp[i - 1][2 * k - 1] + prices[i]。

  根据上面的分析，那么状态转移方程如下（其中j是偶数）：

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

  同理我们最终需要返回的结果就是dp[N][2 * k]。

• 数组初始化

  • 根据我们的分析，在买入之前必须卖出，因此在第一行当中所有的买入状态的价值都是-pirces[0]，所有的卖出状态的价值都是0，因为买入之后再卖出就相当于没有买卖一样。

class Solution { public int maxProfit(int k, int[] prices) { if (prices == null || prices.length == 0) return 0; int m = 2 * k + 1; int[][] dp = new int[prices.length][m]; // dp[i][0] 表示一次买入和卖出都没有 // dp[i][2 * k - 1] 表示第 k 次买入 // dp[i][2 * k] 表示第 k 次卖出 for (int i = 1; i < m; i += 2) { dp[0][i] = -prices[0]; } for (int i = 1; i < prices.length; i++) { dp[i][0] = dp[i - 1][0]; for (int j = 2; j < m; j += 2) { dp[i][j - 1] = Math.max(dp[i - 1][j - 1], dp[i - 1][j - 2] - prices[i]); dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]); } } return dp[prices.length - 1][2 * k]; // 注意数据之前传递依赖的关系 }}

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

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

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

状态表示数组和状态转移方程

和前面的题目一样首先还是需要进行状态的定义和状态转移的分析，在这个问题当中我们用一个二维数组dp[i][j]表示各种不同的状态下的收益，在这个问题当中我们有以下几个状态：

• dp[i][0]，表示在遍历到第i支股票的时候没有进行一次买入和卖出。

  • 在这个时候没有进行买入和卖出，这个时候的收益和遍历到第i-1支股票的时候没有买入和卖出的情况是一样的，他们的收益都等于0，即dp[i][0] = 0，dp[i - 1][0] = 0。

• dp[i][1]，表示在遍历到第i支股票的时候手中含有股票，这个情况可以由三种情况转移过来：

  • 在遍历到第i-1支股票的时候手中已经存在股票了，这个时候只需要保持状态，那么在第i支股票的时候的收益和第i-1支股票的收益是相等的，即dp[i][1] = dp[i - 1][1]。
  • 第二种情况就是在遍历到第i-1支股票的时候手中不存在股票，那么这个时候要想手中存在股票就需要进行买入了，那么就需要花费prices[i]，那么在遍历到第i支股票的时候收益等于dp[i][1] = dp[i - 1][0] - prices[i]。
  • 第三种情况是前一天是处于冷冻期（这里所谈到的冷冻期并不只是前2天卖出，导致的前一天的冷冻期，还有可能是更早之前卖出的，然后保持它的状态，相当于是冷冻期的续期，只不过在续期当中是可以进行买股票的），那么现在是可以进行买入的，即dp[i][1] = dp[i - 1][3] - prices[i]，其中dp[i][3]表示遍历到第i支股票的时候处于冷冻期的收益。
  • 综合以上三种情况：
  dp[i][1]=max(dp[i−1][1],max(dp[i−1][0]−prices[i],dp[i−1][3]−prices[i]))

• dp[i][2]，表示在第i支股票的时候手中不含有股票，可以转移到这个状态的状态一共有两种：

  • 在遍历到第i-1支股票的时候手中本来就不含有股票，那么我们只需要保持状态即可，即dp[i][2] = dp[i - 1][2]。
  • 在遍历到第i-1支股票的时候手中含有股票，那么我们需要将这个股票进行售出，即dp[i][2] = dp[i - 1][1] + prices[i]。
  • 综合以上两种情况：
  dp[i][2]=max(dp[i−1][2],dp[i−1][1]+prices[i])

• dp[i][3]，表示在第i支股票的时候是处在冷冻期，这个状态只能由一个状态转移过来，那就是前一天手中没有股票（因为进行卖出了），即dp[i][3] = dp[i][2]。

数组的初始化和遍历顺序

根据上面的分析我们可以知道，在遍历到第一支股票的时候如果持有股票的话就需要进行买入，那么买入的状态dp[0][1]的值就等于-prices[0]，卖出的状态收益为0，冷冻期的状态也等于0。根据状态转移方程第i行的数据依赖第i-1行，因此从前往后遍历就行。

根据上文当中我们设置的状态，我们能够获取的最大的收益为dp[prices.length - 1][2], dp[prices.length - 1][3]两者当中的一个，因为最终我们要想收益最大手中肯定没有股票，而没有股票的状态有上述提到的两个状态。

class Solution { public int maxProfit(int[] prices) { // dp[i][0] 表示一次买入和卖出操作都没有 这个值始终等于0，可以不用这个状态 // 但是为了完整将这个状态留下来了 // dp[i][1] 表示持有股票 // dp[i][2] 表示不持有股票 // dp[i][3] 卖出操作之后的冷冻期 int[][] dp = new int[prices.length][4]; dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; ++i) { dp[i][1] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][3] - prices[i]), dp[i][0] - prices[i]); // 因为dp[i][0] 始终等于0 因此这里可以直接写 -prices[i] 也行 dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]); dp[i][3] = dp[i - 1][2]; } return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][3]); }}

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

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

状态表示数组和状态转移方程

这道题其实和在这种动态规划你见过吗——状态机动态规划之股票问题(上)当中的第二道题很相似，唯一的区别就是这里加上了手续费，其余部分是一模一样。

现在我们来分析一下如何进行状态的转移：

• dp[i][0]的状态如何从第i-1的状态转移过来：

  • 如果第i-1个状态是手中不存在股票，即dp[i-1][0]，那么第i个状态也没有股票，那么直接是dp[i][0] = dp[i - 1][0]，因为没有进行交易。
  • 如果第i-1个状态手中存在股票，即dp[i-1][1]，那么如果想在第i个状态没有股票，那么就需要将股票卖出，那么收益就为dp[i-1][1] + prices[i]，即dp[i][0] = dp[i-1][1] + prices[i]，但是在这个题目当中会有手续费，我们在卖出的时候需要缴纳手续费，那么我们的收益就变成dp[i][0] = dp[i-1][1] + prices[i] -fee。
  • 综合上面的两种转移方式可以得到下面的转移方程：
  dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i]−fee)

• dp[i][1]的状态如何进行转移：

  • 如果第i-1个状态是手中不存在股票，即dp[i-1][0]，那么我们就需要从第i-1个手中不存在股票的状态进行买入，那么dp[i][0] = dp[i - 1][0] - prices[i]。
  • 如果第i-1个状态手中存在股票，即dp[i-1][1]，而第i个状态有股票，因此不需要进行交易，即dp[i][1]=dp[i - 1][1]。
  • 综合上面的两种转移方式可以得到下面的转移方程：
  dp[i][1]=max(dp[i−1][1],dp[i−1][0]−prices[i]);

• 综合上面的两个状态：

class Solution { public int maxProfit(int[] prices, int fee) { int[][] dp = new int[prices.length][2]; // dp[i][0] 表示不持有股票 // dp[i][1] 表示持有股票 dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; ++i) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[prices.length - 1][0]; }}

综合上面6道题目可以发现像这种题目最困难的地方是寻找对状态的定义和状态转移的分析，一旦能够分析出来这一步，那么后续的操作就变得比较简单了，我们只需要按部就班的根据我们定义的状态和状态转移方程用代码进行实现即可，在写出代码之后我们还可以分析数据之间的依赖关系，通过这种依赖关系或许我们还可以进行空间的优化，这个问题就得具体问题具体分析了！！！

---

更多精彩内容合集可访问项目：https://github.com/Chang-LeHung/CSCore

关注公众号：一无是处的研究僧，了解更多计算机（Java、Python、计算机系统基础、算法与数据结构）知识。