动态规划之买卖股票问题

🌈🌈😄😄

欢迎来到茶色岛独家岛屿，本期将为大家揭晓动态规划之买卖股票问题 ，做好准备了么，那么开始吧。

🌲🌲🐴🐴

• 动态规划算法本质上就是穷举「状态」，然后在「选择」中选择最优解。
• 这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：
• 比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。

时刻牢记「状态」的定义，状态 k 的定义并不是「已进行的交易次数」，而是「最大交易次数的上限限制」。如果确定今天进行一次交易，且要保证截至今天最大交易次数上限为 k，那么昨天的最大交易次数上限必须是 k - 1。

状态转移方程：

base case：
dp[-1][...][0] = dp[...][0][0] = 0
dp[-1][...][1] = dp[...][0][1] = -infinity状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

121. 买卖股票的最佳时机

一、力扣示例

121. 买卖股票的最佳时机 - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

二、解决办法

现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
可以进行进一步化简去掉所有 k：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])

三、代码实现

class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n][2];for (int i = 0; i < n; i++) {if (i - 1 == -1) {// base casedp[i][0] = 0;dp[i][1] = -prices[i];continue;}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[n - 1][0];}
}

 122. 买卖股票的最佳时机 II

一、力扣示例

122. 买卖股票的最佳时机 II - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

二、解决办法

我们发现数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了：
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])

三、代码实现

class Solution {public int maxProfit(int[] prices) {int n=prices.length;int dp[][]=new int[n][2];dp[0][0]=0;dp[0][1]=-prices[0];for(int i=1;i<n;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],dp[i-1][0]-prices[i]);}return dp[n-1][0];}
}

309. 最佳买卖股票时机含冷冻期

一、力扣示例

309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

二、解决办法

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。

三、代码实现

class Solution {public int maxProfit(int[] prices) {int n=prices.length;int dp[][]=new int[n][2];dp[0][0] = 0;dp[0][1] = -prices[0];for(int i=1;i<n;i++){if (i - 2 == -1) {// base case 2dp[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]);continue;}dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i]);}return dp[n-1][0];}
}

 714. 买卖股票的最佳时机含手续费

一、力扣示例

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

二、解决办法

每次交易要支付手续费，只要把手续费从利润中减去即可，改写方程：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] - fee)
解释：相当于买入股票的价格升高了。
在第一个式子里减也是一样的，相当于卖出股票的价格减小了。

三、代码实现

class Solution {public int maxProfit(int[] prices, int fee) {int n = prices.length;int[][] dp = new int[n][2];for (int i = 0; i < n; i++) {if (i - 1 == -1) {// base casedp[i][0] = 0;dp[i][1] = -prices[i] - fee;continue;}dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);}return dp[n - 1][0];}
}

123. 买卖股票的最佳时机 III

一、力扣示例

123. 买卖股票的最佳时机 III - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

二、解决办法

原始的状态转移方程，没有可化简的地方
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

三、代码实现

class Solution {public int maxProfit(int[] prices) {int max_k = 2, n = prices.length;int[][][] dp = new int[n][max_k + 1][2];for (int i = 0; i < n; i++) {for (int k = 1; k <= max_k; k++) {if (i - 1 == -1) {// 处理 base casedp[i][k][0] = 0;dp[i][k][1] = -prices[i];continue;}dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);}}// 穷举了 n × max_k × 2 个状态，正确。return dp[n - 1][max_k][0];}}

 

188. 买卖股票的最佳时机 IV

一、力扣示例

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/

二、解决办法

有了上一题 k = 2 的铺垫，这题应该和上一题的第一个解法没啥区别，你把上一题的 k = 2 换成题目输入的 k 就行了。

但试一下发现会出一个内存超限的错误，原来是传入的 k 值会非常大，dp 数组太大了。那么现在想想，交易次数 k 最多有多大呢？

一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k 没有限制的情况，而这种情况是之前解决过的。

三、代码实现

class Solution {public int maxProfit(int max_k, int[] prices) {int n = prices.length;if (n <= 0) {return 0;}if (max_k > n / 2) {// 复用之前交易次数 k 没有限制的情况return maxProfit_k_inf(prices);}int[][][] dp = new int[n][max_k + 1][2];// k = 0 时的 base casefor (int i = 0; i < n; i++) {dp[i][0][1] = Integer.MIN_VALUE;dp[i][0][0] = 0;}for (int i = 0; i < n; i++) for (int k = max_k; k >= 1; k--) {if (i - 1 == -1) {// 处理 i = -1 时的 base casedp[i][k][0] = 0;dp[i][k][1] = -prices[i];continue;}dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);     }return dp[n - 1][max_k][0];}public int maxProfit_k_inf(int[] prices) {int n = prices.length;int[][] dp = new int[n][2];for (int i = 0; i < n; i++) {if (i - 1 == -1) {// base casedp[i][0] = 0;dp[i][1] = -prices[i];continue;}dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);}return dp[n - 1][0];}
}