【算法 动态规划】买卖股票最佳时机问题

买卖股票的最佳时机含冷冻期（medium）

题目链接

解题思路

分析:

1. 状态表示

依据题目分析得, 第i天结束后, 一共有三种状态:

• 持有股票, 可以是当天买, 也可以是之前买了
• 卖出股票, 当天卖出股票
• 自由状态, 具有买票资格, 但是没有买 (冷冻期的收益相较于前天是不变的, 自由状态是冷冻期的对立面, 所以状态转移不需要用到冷冻期的状态)

2. 状态转移方程

		g[i] = Math.max(g[i-1], f[i-1] - prices[i]);f[i] = Math.max(f[i-1],h[i-1]);h[i] = g[i-1] + prices[i];

3. 初始化

三种状态都会⽤到前⼀个位置的值，因此需要初始化每⼀⾏的第⼀个位置：

• g[0]: 表示第 0 天想要持有股票, 则就需要买入第 0 天的股票 所以 f[0] = -prices[0]
• f[i] = h[i] =0

4. 填表顺序

从左往右填

5. 返回值

    return Math.max(f[n - 1],h[n - 1]);

代码

class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[] g = new int[n]; // 持有股票, 可以是 i-1天就有了, 也可是 i 天买入了int[] f = new int[n]; // 可以买入股票, 但是没有买int[] h = new int[n]; // 该天卖出股票g[0] = -prices[0];for(int i = 1; i < n; ++i) {g[i] = Math.max(g[i-1], f[i-1] - prices[i]);f[i] = Math.max(f[i-1],h[i-1]);h[i] = g[i-1] + prices[i];}return Math.max(f[n - 1],h[n - 1]);}
}

买卖股票的最佳时期含⼿续费（medium）

题目链接

解题思路

1. 状态表示

由于有「买⼊」「可交易」两个状态，因此我们可以选择⽤两个数组，其中：

• f[i] 表⽰：第 i 天结束后，处于「买⼊」状态，此时的最⼤利润；
• g[i] 表⽰：第 i 天结束后，处于「卖出」状态，此时的最⼤利润。

2. 状态转移方程

我们选择在「卖出」的时候，⽀付这个⼿续费，那么在「买⼊」的时候，就不⽤再考虑⼿续费的问题。

• 对于 f[i] ，我们有两种情况能到达这个状态：

  • 在 i - 1 天「持有」股票，第 i 天啥也不⼲。此时最⼤收益为 f[i - 1] ；
  • 在 i - 1 天的时候「没有」股票，在第 i 天买⼊股票。此时最⼤收益为 g[i - 1] - prices[i]) ；

  两种情况下应该取最⼤值，因此 f[i] = max(f[i - 1], g[i - 1] - prices[i]) 。

• 对于 g[i] ，我们也有两种情况能够到达这个状态：

  • 在 i - 1 天「持有」股票，但是在第 i 天将股票卖出。此时最⼤收益为： f[i - 1] + prices[i] - fee) ，记得⼿续费；
  • 在 i - 1 天「没有」股票，然后第 i 天啥也不⼲。此时最⼤收益为： g[i - 1] ；

两种情况下应该取最⼤值，因此 g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee) 。

3. 初始化：

由于需要⽤到前⾯的状态，因此需要初始化第⼀个位置。

• 对于 f[0] ，此时处于「买⼊」状态，因此 f[0] = -prices[0] ；
• 对于 g[0] ，此时处于「没有股票」状态，啥也不⼲即可获得最⼤收益，因此 g[0] = 0 。

4. 填表顺序：

毫⽆疑问是「从左往右」，但是两个表需要⼀起填。

5. 返回值：

应该返回「卖出」状态下，最后⼀天的最⼤值收益： g[n - 1] 。

代码

买卖股票的最佳时机III（hard）

题目链接

解题思路

1. 状态表示

我们依旧可分为两种状态:

• f 表示持有股票状态
• g 表示卖出股票状态

不同的是, 多出了至多只能交易 k = 2 两次

所以可以这样定义状态:

• f[i][j]: 表示在第 i 天结束的时候, 一共交易了 j 次, 持有股票的状态下最大的利益
• g[i][j]: 表示在第 i 天结束的时候, 一共交易了 j 次, 卖出股票的状态下最大的利益

这里规定: 当卖出股票的时候, 才算结束一次完整的交易

2. 状态转移方程

对于 f[i][j]:

• 在 i - 1 天的时候，交易了 j 次，处于「买⼊」状态，第 i 天啥也不⼲即可。此时最⼤利润为： f[i - 1][j] ；
• 在 i - 1 天的时候，交易了 j 次，处于「卖出」状态，第 i 天的时候把股票买了。此时的最⼤利润为： g[i - 1][j] - prices[i] 。

综上，我们要的是「最⼤利润」，因此是两者的最⼤值： f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]) 。

对于 g[i][j] ，我们也有两种情况可以到达这个状态：

• 在 i - 1 天的时候，交易了 j 次，处于「卖出」状态，第 i 天啥也不⼲即可。此时的最⼤利润为： g[i - 1][j] ；
• 在 i - 1 天的时候，交易了 j - 1 次，处于「买⼊」状态，第 i 天把股票卖了，然后就完成了 j ⽐交易。此时的最⼤利润为： f[i - 1][j - 1] + prices[i] 。但是这个状态不⼀定存在，要先判断⼀下。

综上，我们要的是最⼤利润，因此状态转移⽅程为：

g[i][j] = g[i - 1][j];
if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);

3. 初始化：

由于需要⽤到 i = 0 时的状态，因此我们初始化第⼀⾏即可。

• 当处于第 0 天的时候，只能处于「买⼊过⼀次」的状态，此时的收益为 -prices[0] ，因此 f[0][0] = - prices[0] 。
• 为了取 max 的时候，⼀些不存在的状态「起不到⼲扰」的作⽤，我们统统将它们初始化为 -INF （⽤ INT_MIN 在计算过程中会有「溢出」的⻛险，这⾥ INF 折半取0x3f3f3f3f ，⾜够⼩即可）

4. 填表顺序：

从「上往下填」每⼀⾏，每⼀⾏「从左往右」，两个表「⼀起填」。

5. 返回值：

返回处于「卖出状态」的最⼤值，但是我们也「不知道是交易了⼏次」，因此返回 g 表最后⼀⾏的最⼤值。

代码

class Solution {public int maxProfit(int[] prices) {int INF = 0x3f3f3f3f;int n = prices.length;int[][] f = new int[n][3];int[][] g = new int[n][3];for(int j = 0; j < 3; j++) f[0][j] = g[0][j] = -INF;g[0][0] = 0;f[0][0] = -prices[0];int max = 0;for(int i=1;i<n; ++i) {for(int j =0;j<3;++j) {f[i][j] = Math.max(f[i-1][j],g[i-1][j] - prices[i]);g[i][j] = g[i-1][j];if(j>=1) {g[i][j] = Math.max(g[i][j],f[i-1][j-1] + prices[i]);}}}for(int j =0;j<3;++j) max = Math.max(max,g[n-1][j]);return max;}
}

买卖股票的最佳时机IV（hard）

题目链接

解题思路

和上一题一样, 只要将 2次交易 换成 k次交易 既可以解决问题

代码

class Solution {public int maxProfit(int k, int[] prices) {int n = prices.length;int INF = 0x3f3f3f3f;int[][] f = new int[n][k+1];int[][] g = new int[n][k+1];for(int j = 0; j < k+1; ++j) {f[0][j] = g[0][j] = -INF;}f[0][0] = -prices[0];g[0][0] = 0;for(int i = 1; i < n; ++i) {for(int j = 0; j < k+1; ++j) {f[i][j] = Math.max(f[i-1][j],g[i-1][j] - prices[i]);g[i][j] = g[i-1][j];if(j>=1)g[i][j] = Math.max(g[i][j],f[i-1][j-1] + prices[i]);}}int max = 0;for(int j=0;j<k+1;++j) {max = Math.max(max,g[n-1][j]);}return max;}
}