动态规划之买卖股票问题
🌈🌈😄😄
欢迎来到茶色岛独家岛屿，本期将为大家揭晓动态规划之买卖股票问题 ，做好准备了么，那么开始吧。
🌲🌲🐴🐴
- 动态规划算法本质上就是穷举「状态」，然后在「选择」中选择最优解。
- 这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的
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];}
}
