代码随想录算法训练营第四十九天 | LeetCode 123. 买卖股票的最佳时机 III、188. 买卖股票的最佳时机 IV
1. LeetCode 123. 买卖股票的最佳时机 III
1.1 思路
- 121. 买卖股票的最佳时机是在数组中只能买卖一次，122. 买卖股票的最佳时机 II是在数组中可以买卖多次，本题是在数组中至多买卖 2 次，可以 0 次、1 次、2 次
- dp 数组及其下标的含义：第 i 天 dp[i][0] 表示不操作，dp[i][1] 表示第 1 次持有，不一定是在第 i 天才买入的，因此是持有，dp[i][2] 表示第 1 次不持有，dp[1][3] 表示第 2 次持有，dp[i][4] 表示第 2 次不持有。以上就是本题的 5 种状态都表示出来了
- 递推公式：dp[i][0]=dp[i-1][0]，由前一天延续下来；dp[i][1]=Math.max（dp[i-1][1]，dp[i-1][0]-prices[i]）即延续前一天持有的状态，或者由前一天不操作然后买入变为第 1 次持有，取最大值是因为求的是手头上最多的现金；dp[i][2]=Math.max（dp[i-1][2]，dp[i-1][1]+prices[i]）即延续前一天不持有的状态，或者由前一天第 1 次持有然后卖出变为第 1 次不持有；dp[i][3]=Math.max（dp[i-1][3]，dp[i-1][2]-prices[i]）即延续前一天持有的状态，或者由前一天第 1 次不持有然后买入变为第 2 次持有的；dp[i][4]=Math.max（dp[i-1][4]，dp[i-1][3]+prices[i]）即延续前一天不持有的状态，或者由前一天第 2 次持有然后卖出变为第 2 次不持有的
- dp 数组的初始化：从递推公式可以看出都是由前一个状态推导出来的，因此 dp[0][0]=0 因为没操作， dp[0][1]=0-prices[0] 因为第 1 次持有， dp[0][2]=0 因为第 1 次不持有，可以理解为第 0 天买入又在第 0 天卖出了，这是可以的， dp[0][3]=0-prices[i] 因为第 2 次持有，第 1 次的持有与不持有都在同一天买入和卖出了，dp[0][4]=0 因为第 2 次不持有，同理是第 0 天买入和卖出了
- 遍历顺序：从递推公式可以看出从前往后 for（int i=1；i<length；i++）从 1 开始是因为第 0 天已经初始化了。最终因为不持有的状态就是卖出了的状态肯定比持有还没卖出的状态有钱，因此是返回 dp[i][2] 和 dp[i][4] 之间取最大值。其实直接返回 dp[length-1][4] 也可以，这里就包括了 dp[length-1][2] 了。你可能疑惑我在第 1 次卖出的时候就是最大值了，其实没关系，如果这个是最大值了，那我再当天买入再卖出也同样是最大值，这就是 dp[length-1][4] 包括了 dp[length-1][2]
- 打印 dp 数组：用于 debug
1.2 代码
class Solution { public int maxProfit(int[] prices) { int len = prices.length; // 边界判断, 题目中 length >= 1, 所以可省去 if (prices.length == 0) return 0; /* * 定义 5 种状态: * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出 */ int[][] dp = new int[len][5]; dp[0][1] = -prices[0]; // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润 dp[0][3] = -prices[0]; for (int i = 1; i < len; i++) { dp[i][1] = Math.max(dp[i - 1][1], -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[len - 1][4]; } }
2. LeetCode 188. 买卖股票的最佳时机 IV
2.1 思路
- 在123. 买卖股票的最佳时机 III中我们至多只能买卖两次，本题是至多买卖 k 次。其实两题联系是很紧密的。
- dp 数组及其下标的含义：在123. 买卖股票的最佳时机 III中至多买卖 2 次就已经列到了 dp[i][4] 了，因为买卖一次就要有一次买入一次卖出。因此至多买卖 k 次的话每多一次就要多 2 个空位表示状态，因此 dp 数组应该定义成 dp[prices.length][2k+1] 第一维度就是数组大小，第二维度就是 2k+1 这么大，因为下标到 2k+1 这么大。dp 数组的含义和123. 买卖股票的最佳时机 III是一样的，可以看出规律第二维度的数字如果是奇数就是持有，偶数就是不持有。比如 dp[i][1] 就是持有，dp[i][2] 就是不持有
- 递推公式：我们需要一个 for循环才能把这些状态都表示出来。第二维度的下标都用 j 表示 for（int i=0；i<prices.length；i++）for（int j=0；j<2k；j+=2）持有状态：dp[i][j+1]=Math.max（dp[i-1][j+1]，dp[i-1][j]-prices[i]）这里即从前一天持有的状态延续，或者由前一天不持有的状态买入变为持有；不持有状态：dp[i][j+2]=Math.max（dp[i-1][j+2]，dp[i-1][j+1]+prices[i]）这里即从前一天不持有的状态延续，或者由前一天持有的状态卖出变为不持有。j 这层 for循环后面 j<2k 是因为我们在下面进行了加一，比如 k 等于 2，那 dp[i][1] 和 dp[i][2] 都是 k=1 时的状态，dp[i][3] 和 dp[i][4] 都是 k=2 时的状态
- dp 数组的初始化：根据递推公式初始化第 0 天的状态，第二维度的下标的状态是在只有奇数的情况才会 0-prices[i]，都表示为第几次持有，就通过 for（int j=1；j<2k；j+=2）dp[0][j]=0-prices[i]，这里 j 从 1 开始是因为 dp[0][1] 是第 1 次买入持有，从这里开始，为什么 j<2k，同样代入个数字，k=2 时，j=3<2*2 同样可以把 dp[0][3] 这个奇数的情况初始化
- 遍历顺序：从前往后遍历
- 打印 dp 数组：用于 debug
2.2 代码
// 版本二: 二维 dp数组 class Solution { public int maxProfit(int k, int[] prices) { if (prices.length == 0) return 0; // [天数][股票状态] // 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作 int len = prices.length; int[][] dp = new int[len][k*2 + 1]; // dp数组的初始化, 与版本一同理 for (int i = 1; i < k*2; i += 2) { dp[0][i] = -prices[0]; } for (int i = 1; i < len; i++) { for (int j = 0; j < k*2 - 1; j += 2) { dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]); dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); } } return dp[len - 1][k*2]; } }
