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

状态机动静布局之股票问题总结

前言

在后面的三篇股票问题的文章当中咱们一共介绍了 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]);
  $$

• 综合下面的两个状态：

$$
\begin{cases}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]);
\end{cases}
$$

参考代码如下：

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][j] = max(dp[i – 1][j], dp[i – 1][j – 1] \pm 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] 两者当中的一个，因为最终咱们要想收益最大手中必定没有股票，而没有股票的状态有上述提到的两个状态。

$$
max(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]);
  $$

• 综合下面的两个状态：

$$
\begin{cases}dp[i][0] = max(dp[i – 1][0], dp[i – 1][1] + prices[i] -fee)\\
dp[i][1] = max(dp[i – 1][1], dp[i – 1][0] – prices[i]);
\end{cases}
$$

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-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。