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

这种动静布局你见过吗——状态机动静布局之股票问题(下)

前言

在后面的两篇文章这种动静布局你见过吗——状态机动静布局之股票问题 (上) 和这种动静布局你见过吗——状态机动静布局之股票问题 (中) 曾经谈了 4 道和股票问题相干的题目，具体解释了 状态机动静布局 和他的基本原理和利用形式。在本篇文章当中，会再介绍剩下的两道股票问题，持续深刻和学习 状态机动静布局。

最佳交易股票机会含冷冻期

题目

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

设计一个算法计算出最大利润。在满足以下约束条件下，你能够尽可能地实现更多的交易（屡次交易一支股票）: 卖出股票后，你无奈在第二天买入股票 (即冷冻期为 1 天)。

留神：你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。

示例

示例 1:

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

示例 2:

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

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

和后面的题目一样首先还是须要进行状态的定义和状态转移的剖析，在这个问题当中咱们用一个二维数组 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]);
  }
}

因为 dp[i][0] 始终等于 0，所以将所有含 dp[i][0] 的中央都能够删除，因而上面的代码也是正确的。

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]),
          -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]);
  }
}

数组优化——滚动数组

在下面的状态转移方程当中咱们始终只应用了两行的数据，因而咱们能够只应用一个两行的二维数组，而后进行交替应用（对 i 求 2 的余数就能够了）就能够了，代码如下：

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

交易股票的最佳时机含手续费

题目

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

你能够有限次地实现交易，然而你每笔交易都须要付手续费。如果你曾经购买了一个股票，在卖出它之前你就不能再持续购买股票了。

返回取得利润的最大值。

留神：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只须要为领取一次手续费。

示例

示例 1

输出：prices = [1, 3, 2, 8, 4, 9], fee = 2
输入：8
解释：可能达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2

输出：prices = [1,3,7,5,10,3], fee = 3
输入：6

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

这道题其实和在这种动静布局你见过吗——状态机动静布局之股票问题 (上) 当中的第二道题很类似，惟一的区别就是这里加上了手续费，其余部分是截然不同。

当初咱们来剖析一下如何进行状态的转移：

• 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];
  }
}

数组优化——滚动数组

class Solution {public int maxProfit(int[] prices, int fee) {int[][] dp = new int[2][2];
    // dp[i][0] 示意不持有股票
    // dp[i][1] 示意持有股票
    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] - fee);
      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];
  }
}

再优化

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

下面的代码优化和这种动静布局你见过吗——状态机动静布局之股票问题 (中) 当中的优化原理是一样的。在上面的代码当中，右边的单行数组 dp[0] 和 dp[1]相当于二维数组当中的 dp[i][0]，dp[i][1]，左边的单行数组dp[0] 和 dp[1]相当于二维数组的 dp[i - 1][0] 和 dp[i - 1][1]。

dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee);
dp[1] = Math.max(dp[1], dp[0] - prices[i]);

然而咱们会发现下面代码的第二行会依赖 dp[0]，这个dp[0] 是第 i-1 行的状态，然而 dp[0] 在第一行曾经产生了更新，也就是说 dp[0] 曾经更新到了第 i 行的状态，那么为什么后果是对的呢？咱们能够依据上面三条规定进行剖析：

• 如果 dp[0] 取的是 dp[0]，也就是说dp[0] > dp[1] + prices[i] - fee ，那么dp[0] 还是上一行的状态，并不影响 dp[1] 的后果。
• 如果 dp[0] 取的是 dp[1] + prices[i] - fee，然而dp[1] 取的是上一行的 dp[1] 那么对后果也没有什么影响。
• 如果 dp[0] 取的是 dp[1] + prices[i] - fee 而且 dp[1] 取的是 dp[0] - prices[i]，那么就有影响了，然而这一加一减其实没有意义，还单纯的须要缴纳手续费，最终dp[0] - prices[i] = dp[1] + prices[i] - fee - prices[i] = dp[1] - fee < dp[1] ，因而这个状态不会被最终的后果取到，被取到的状态必定都是第i-1 行的 dp[1]（因为dp[1] 更大），也就是说这个状态又会转移到第二条当中，因而对最终的后果没有影响。

总结

在本篇文章当中次要跟大家介绍了最初两道股票问题，第一道题的状态转移还是比较复杂的，可能须要大家认真进行领会，能力了解，尤其是对于冷冻期的状态的转换可能比拟绕。本文当中的第二道题目跟之前的题目十分像，只须要在收益上减去手续费即可。置信看完这三篇文章，做完这六道题目你对 状态机动静布局 的基本原理曾经很理解了，它和传统的动静布局最不一样的就是有很多简单的状态之间的转换，而且个别的动静布局的题目都是多重循环，然而在 状态机动静布局 当中是单循环。

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

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