关于动态规划:这种动态规划你见过吗状态机动态规划之股票问题中

前言

在后面的文章这种动静布局你见过吗——状态机动静布局之股票问题 (上) 咱们曾经介绍了两个根本的股票问题，并且对 状态机动静布局 做出了简要的介绍，以及在 状态机 当中的状态是如何进行转换的，然而在后面的两个问题当中 状态 的个数比拟少，可能不不便大家了解 状态机 的含意，在本篇文章所谈到的两个问题当中状态的数目还是比拟多的，因而对于大家深刻了解 状态机动静布局 可能会好一点。

卖股票的最佳时机 III

题目

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多能够实现 两笔 交易。留神：你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。

示例

示例 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 天接连购买股票，之后再将它们卖出。因为这样属于同时参加了多笔交易，你必须在再次购买前发售掉之前的股票。

这道题目跟之前的两道题目不同之处在于，在上篇文章当中的两道题要么是可能购买一次，要么可能购买无数次，而在本道题目当中只可能购买两次，在这种状况下咱们应该如何定义各种状态呢？

状态示意数组和状态转移

在这道题目当中咱们也是二维数组进行状态的示意，二维数组为 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]);

动静规划设计

在求解动静布局问题的时候通常的步骤有以下几个：

• 寻找可能示意状态的数组 dp，即咱们须要寻找dp 的含意，剖析须要用几纬数组示意具体的状态。
• 通过剖析问题，寻找动静转移公式。
• 初始化状态数组。
• 通过剖析动静转移方程，确定数组的遍历程序。

在前文当中咱们曾经实现了前两步，当初须要对数组进行初始化，第一天咱们能够不买入一只股票，那么第一天咱们的收益为 0，即dp[0][0] = 0，咱们也能够买入一只股票，即dp[0][1] = -prices[0]，咱们能够买入一只再卖出，那等于不买，因为同一天价格都一样，即dp[0][2] = 0，咱们也能够二次买入，也就是先买入再卖出再买入，即dp[0][3] = -prices[0]，同样的咱们也能够进行两次买入卖出，最终的收益也等于 0，即dp[0][4] = 0。

综合下面的剖析，咱们的初始化代码如下：

dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][3] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;

依据状态转移方程，咱们晓得第 i 天依赖于第 i-1 天的数据，因而咱们遍历的程序为从前到后进行遍历。

代码

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] 的最大值
    // ......
  }
}

下面的代码的工夫和空间复杂度别离为 $O(n)$ 和 $O(n)$。

空间复杂度优化

其实咱们能够应用一个单行数组进行优化，优化代码如下：

class Solution {public int maxProfit(int[] prices) {int[] dp = new int[5];
    dp[1] = -prices[0];
    dp[3] = -prices[0];
    for (int i = 1; i < prices.length; i++) {dp[0] = dp[0]; // 这一行能够不要的 放在这里只是为了状态转移方程的残缺
      dp[1] = Math.max(dp[1], dp[0] - prices[i]);
      dp[2] = Math.max(dp[2], dp[1] + prices[i]);
      dp[3] = Math.max(dp[3], dp[2] - prices[i]);
      dp[4] = Math.max(dp[4], dp[3] + prices[i]);
    }
    return dp[4];
  }
}

咱们当初来简要剖析一下下面的代码为什么可行：

比方当初 i=3，当初要进行更新，当初的dp 数组还是 i=2 的状态，如果用二维数组来示意的话，当初的单行数组中的 dp[i] 相当于二维数组当中的数据 dp[2][i]，如果咱们当初须要更新dp[3][2]，依据二维数组的动静转移方程，咱们须要二维数组第二行的数据dp[2][2]，然而此时的单行数组当中的数据还没有更新，也就是说dp[2] 等于 dp[2][2]（后面的dp 示意单行数组，前面的 dp 表示意二维数组的dp），因而还是上一个状态的数据，因而更新没有问题。

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[3][2] 依赖于 dp[2][1]，而dp[2][1] 相当于 dp[1]，然而在上面的代码当中，咱们在更新dp[2] 之前 dp[1] 曾经更新了，也就是说 dp[1] 曾经是第三行的状态了，即dp[1] = dp[3][1]，而当初更新的时候须要的是第二行的状态，因而这就不对了。

class Solution {public int maxProfit(int[] prices) {int[] dp = new int[5];
    dp[1] = -prices[0];
    dp[3] = -prices[0];
    for (int i = 1; i < prices.length; i++) {dp[0] = dp[0]; // 这一行能够不要的 放在这里只是为了状态转移方程的残缺
      dp[1] = Math.max(dp[1], dp[0] - prices[i]);
      dp[2] = Math.max(dp[2], dp[1] + prices[i]);
      dp[3] = Math.max(dp[3], dp[2] - prices[i]);
      dp[4] = Math.max(dp[4], dp[3] + prices[i]);
    }
    return dp[4];
  }
}

那为什么下面的代码又可行呢？

• 如果 dp[1] 是从上一行的 dp[1] 转移而来，那么就是合乎咱们的想法的，dp[2]应用的还是上一个 (第 2 行) 状态的 dp[1]，因为本行状态的(第 3 行)dp[1] 和第 2 行的 dp[1] 相等。
• 如果 dp[1] 是从 dp[0] - prices[3] 转移过去的，那么在这条语句 dp[2] = Math.max(dp[2], dp[1] + prices[3]); 当中，如果抉择的是 dp[2] 那么也没关系，因为他跟 dp[1] 没有关系。如果抉择的是 dp[1] + prices[3]，那么也没关系因为dp[1] 减去了 prices[3]，这一加一减相当于没有收益，这并不影响最初的后果，因为这一卖一买都是在明天实现的，而对最终后果产生影响的必定是在后面曾经买入的操作（比方第 2 行的dp[1] 就示意在之前进行第一次买入），而不会是在明天的买入，了解这一点就能够了解上的代码了。
• 其余代码的影响也是相似的，都能够通过一加一减低消掉，最终都不影响最初的后果。

通过上述的优化之后空间复杂度变为 $O(1)$。

卖股票的最佳时机 IV

题目

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

示例

示例 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。

问题剖析

这个问题和本文当中的第一个问题其实差不多，只不过下面的问题是最多实现两笔交易，而在这个问题当中是最多能够实现 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];
    // 留神数据之前传递依赖的关系
  }

}

总结

在本篇文章当中次要给大家介绍了另外两种股票问题，在这两个股票问题当中都有许多的状态，状态之间的转化也比较复杂，在仔细分析下面两个问题的状态转化之后置信你曾经可能了解 状态机动静布局 了，这种含有比较复杂的状态之间的变动就叫做 状态机动静布局，这种问题个别剖析起来还是比较复杂的。

更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

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