Day43——Dp专题 红太狼 2024-03-30 10:01 27阅读 0赞 #### 文章目录 #### * * 股票问题篇 * * 21、买卖股票的最佳时机 * 22、买卖股票的最佳时机II * 23、买卖股票的最佳时机Ⅲ * 24、买卖股票的最佳时机Ⅳ * 25、最佳买卖股票时机含冷冻期 * 26、买卖股票的最佳时机含手续费 * 股票问题总结篇 * * -------------------- ### 股票问题篇 ### #### 21、买卖股票的最佳时机 #### [力扣题目链接][Link 1] **动态规划** 定义二维数组:`dp[n][2]` **状态表示**: `dp[i][0]`表示第`i`天没有持有股票所得最大现金(利润) `dp[i][1]`表示第`i`天持有股票所得最大现金(利润) **状态计算**: * `dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]` * `dp[i][1] = max(dp[i - 1][1], -prices[i])` * 第`i-1`天就持有股票,那么就保持现状(不买入),所得现金就是昨天持有股票的所得现金 即:`dp[i - 1][1]` * 第`i`天买入股票(买入),所得现金就是买入今天的股票后所得现金即:`-prices[i]` **初始化**: * `f[0][1] = -prices[0];` * `f[0][0] = 0;` 结果返回:`f[n - 1][0]`:最后一天不持有股票的最大利润(要么买了股票然后卖出去赚钱了,要么没买即为0) **Code** class Solution { public int maxProfit(int[] prices) { if(prices==null||prices.length==0){ return 0; } int n = prices.length; int[][] dp = new int[n][2]; dp[0][1] = -prices[0]; dp[0][0] = 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],-prices[i]); } return dp[n - 1][0]; } } #### 22、买卖股票的最佳时机II #### [力扣题目链接][Link 2] 本题和题I的唯一区别本题股票可以买卖多次了(注意只有一只股票,所以再次购买前要出售掉之前的股票)! **动态规划** 定义二维数组:`dp[n][2]` **状态表示**: `dp[i][0]`表示第`i`天没有持有股票所得最大现金(利润) `dp[i][1]`表示第`i`天持有股票所得最大现金(利润) **状态计算**: * `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])`——Ⅰ * 第`i-1`天就持有股票,那么就保持现状(不买入),所得现金就是昨天持有股票的所得现金 即:`dp[i - 1][1]` * 第`i`天买入股票(买入),所得现金就是买入今天的股票后所得现金即:`dp[i - 1][0]-prices[i])` **初始化**: * `f[0][1] = -prices[0];` * `f[0][0] = 0;` 结果返回:`f[n - 1][0]`:最后一天不持有股票的最大利润(要么买了股票然后卖出去赚钱了,要么没买即为0) **对比Ⅰ和Ⅱ买卖股票的最佳时机** `dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]-prices[i])` `dp[i][1] = max(dp[i - 1][1], -prices[i])` 原因就是`II`可以买卖多次就要积累前面赚到的最大利润,而`I`只能买卖一次,刚刚买入时利润必定是`-prices[i]` **Code** **二维数组** class Solution { public int maxProfit(int[] prices) { if(prices==null||prices.length==0){ return 0; } int n = prices.length; int[][] dp = new int[n][2]; dp[0][1] = -prices[0]; dp[0][0] = 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]; } } **一维数组** // 优化空间 class Solution { public int maxProfit(int[] prices) { int[] dp = new int[2]; dp[1] = -prices[0]; dp[0] = 0; for(int i = 1; i < prices.length; i++){ dp[1] = Math.max(dp[1], dp[0] - prices[i]); dp[0] = Math.max(dp[0], dp[1] + prices[i]); } return dp[0]; } } #### 23、买卖股票的最佳时机Ⅲ #### [力扣题目链接][Link 3] **动规五部曲** * **确定dp数组以及下标含义** 1. 没有操作 2. 第一次买入 3. 第一次卖出 4. 第二次买入 5. 第二次卖出 `dp[i`\]\[j\]中 i表示第i天,j为 \[0 - 4\] 五个状态,`dp[i][j]`表示第i天状态j所剩最大现金 * **确定递推公式** `dp[i][1]`,表示的是第i天,买入股票的状态,并不是说一定要第i天买入股票,有可能i-1天买的股票 达到`dp[i`\]\[1\]状态,有两个具体操作: * 操作一:第i天买入股票了,那么`dp[i][1] = dp[i-1][0] - prices[i]` * 操作二:第i天没有操作,而是沿用前一天买入的状态,即:`dp[i][1] = dp[i - 1][1]` 同理`dp[i][2]`也有两个操作: * 操作一:第i天卖出股票了,那么`dp[i][2] = dp[i - 1][1] + prices[i]` * 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:`dp[i][2] = dp[i - 1][2]` **每次dp第一种是上一个状态的延续,还有一种为本次的改变(买入或卖出)** 同理可推出剩下状态部分: `dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);` `dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[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]); * **dp数组初始化** 第0天没有操作,这个最容易想到,就是0,即:`dp[0][0] = 0;` 第0天做第一次买入的操作,`dp[0][1] = -prices[0];` **存在一种情况当天买,当天卖** * 第一次持有或第二次持有 dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; * 第一次不持有或第二次不持有 dp[0][2] = 0; dp[0][4] = 0; * **确定遍历顺序** 从递归公式其实已经可以看出,一定是从前向后遍历,因为dp\[i\],依靠`dp[i - 1]`的数值。 * **举例并推导dp数组** ![image-20221212220237134][] 现在最大的时候一定是卖出的状态,而两次卖出的状态现金最大一定是最后一次卖出。 所以最终最大利润是`dp[n-1][4]` **Code** **二维** class Solution { public int maxProfit(int[] prices) { int n = prices.length; if(prices==null||n==0){ return 0; } int[][] dp = new int[n][5]; dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for(int i = 1; i < n; 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[n-1][4]; } } **一维** class Solution { public int maxProfit(int[] prices) { int[] dp = new int[5]; dp[1] = -prices[0]; dp[3] = -prices[0]; for(int i = 1; i < prices.length; i++){ dp[1] = Math.max(dp[1], -prices[i]); dp[2] = Math.max(dp[2], dp[1]+prices[i]); dp[3] = Math.max(dp[3], dp[2]-prices[i]); dp[4] = Math.max(dp[4], dp[3]+ prices[i]); } return dp[4]; } } #### 24、买卖股票的最佳时机Ⅳ #### [力扣题目链接][Link 4] 本题与Ⅲ的区别在于买卖股票k次,就是将Ⅲ抽象出来 **动规五部曲** * **确定dp数组以及下标的含义** 使用二维数组 `dp[i][j]` :第i天的状态为j,所剩下的最大现金是`dp[i][j]` j的状态表示为: * 0 表示不操作 * 1 第一次买入 * 2 第一次卖出 * 3 第二次买入 * 4 第二次卖出 * j+1就是买入,j+2就是卖出 **除了0以外,偶数就是卖出,奇数就是买入**。 * **确定递推公式** dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]); dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); * **dp数组初始化** `dp[0`\]\[j\]当j为奇数的时候都初始化为 -prices\[0\],j为偶数的时候都初始化为0 * **确定遍历顺序** 一定是从前向后遍历,因为dp\[i\],依靠dp\[i - 1\]的数值。 * **举例并推导dp数组** ![image-20221214195453126][] 最后一次卖出,一定是利润最大的,`dp[prices.size() - 1][2 * k]`即红色部分就是最后求解 **Code** **二维**:股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作 class Solution { public int maxProfit(int k, int[] prices) { if(prices==null||prices.length==0){ return 0; } int n = prices.length; int[][] dp = new int[n][2*k+1]; for(int j = 1;j < 2*k; j += 2){ dp[0][j] = -prices[0]; } for(int i = 1;i < n;i++){ for(int j = 0;j < 2*k;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[n - 1][2*k]; } } **一维**(参考) class Solution { public int maxProfit(int k, int[] prices) { if(prices.length == 0){ return 0; } if(k == 0){ return 0; } // 其实就是123题的扩展,123题只用记录2次交易的状态 // 这里记录k次交易的状态就行了 // 每次交易都有买入,卖出两个状态,所以要乘 2 int[] dp = new int[2 * k]; // 按123题解题格式那样,做一个初始化 for(int i = 0; i < dp.length / 2; i++){ dp[i * 2] = -prices[0]; } for(int i = 1; i <= prices.length; i++){ dp[0] = Math.max(dp[0], -prices[i - 1]); dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]); // 还是与123题一样,与123题对照来看 // 就很容易啦 for(int j = 2; j < dp.length; j += 2){ dp[j] = Math.max(dp[j], dp[j - 1] - prices[i-1]); dp[j + 1] = Math.max(dp[j + 1], dp[j] + prices[i - 1]); } } // 返回最后一次交易卖出状态的结果就行了 return dp[dp.length - 1]; } } #### 25、最佳买卖股票时机含冷冻期 #### [力扣题目链接][Link 5] **动规五部曲** * **确定dp数组以及下标的含义** `dp[i][j]`,第i天状态为j,所剩的最多现金为`dp[i][j]`。 * **确定递推公式** * 状态一:买入股票状态(今天买入股票,或者是之前就买入了股票然后没有操作)`dp[i][0]` * 卖出股票状态,这里就有两种卖出股票状态 * 状态二:两天前就卖出了股票,度过了冷冻期,一直没操作,今天保持卖出股票状态`dp[i][1]` * 状态三:今天卖出了股票`dp[i][2]` * 状态四:今天为冷冻期状态,但冷冻期状态不可持续,只有一天!`dp[i][3]` **达到买入股票状态(状态一)即:`dp[i`\]\[0\],有两个具体操作:** * 操作一:前一天就是持有股票状态(状态一),`dp[i][0] = dp[i - 1][0]` * 操作二:今天买入了,有两种情况 * 前一天是冷冻期(状态四),`dp[i - 1][3] - prices[i]` * 前一天是保持卖出股票状态(状态二),`dp[i - 1][1] - prices[i]` 所以操作二取最大值,即:`max(dp[i - 1][3], dp[i - 1][1]) - prices[i]` 那么`dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);` 达到保持卖出股票状态(状态二)即:`dp[i][1]`,有两个具体操作: * 操作一:前一天就是状态二 * 操作二:前一天是冷冻期(状态四) `dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])`; 达到今天就卖出股票状态(状态三),即:`dp[i][2]` ,只有一个操作: * 操作一:昨天一定是买入股票状态(状态一),今天卖出 即:`dp[i][2] = dp[i - 1][0] + prices[i]`; 达到冷冻期状态(状态四),即:`dp[i][3]`,只有一个操作: * 操作一:昨天卖出了股票(状态三) `dp[i][3] = dp[i - 1`\]\[2\]; 综上分析,递推代码如下: dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][1] - prices[i],dp[i-1][3] - prices[i])); dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]); dp[i][2] = (dp[i-1][0] + prices[i]); dp[i][3] = (dp[i-1][2]); * **dp数组初始化** 对于在定义中没有意义的数组,可通过递推公式确定 dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0; dp[0][3] = 0; * **确定遍历顺序** 从递归公式上可以看出,`dp[i] 依赖于 dp[i-1]`,所以是从前向后遍历。 * **举例并推导dp数组** ![image-20221217111152412][] **取最大值** return Math.max(dp[n-1][1],Math.max(dp[n-1][2],dp[n-1][3])); **Code** class Solution { public int maxProfit(int[] prices) { if(prices==null|prices.length==0) return 0; int n = prices.length; int[][] dp = new int[n][4]; dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0; dp[0][3] = 0; for(int i = 1;i < n;i++){ dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][1] - prices[i],dp[i-1][3] - prices[i])); dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]); dp[i][2] = (dp[i-1][0] + prices[i]); dp[i][3] = (dp[i-1][2]); } return Math.max(dp[n-1][1],Math.max(dp[n-1][2],dp[n-1][3])); } } #### 26、买卖股票的最佳时机含手续费 #### [力扣题目链接][Link 6] **动规五部曲** * **确定dp数组以及下标的含义** \`\`dp\[i\]\[j\]\`表示第i天的状态为j,所剩的最多现金 * **确定递推公式** `dp[i][0]` 表示第i天持有股票所剩最多现金。 `dp[i][1]` 表示第i天不持有股票所得最多现金 如果第i天持有股票即`dp[i][0]`, 那么可以由两个状态推出来 * 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:`dp[i - 1][0]` * 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:`dp[i - 1][1] - prices[i]` 在来看看如果第i天不持有股票即`dp[i][1]`的情况, 依然可以由两个状态推出来 * 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:`dp[i - 1][1]` * 第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金即:`dp[i - 1][0] + prices[i] - fee` 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); * **dp数组初始化** dp[0][0] = -prices[0]; dp[0][1] = 0; * **确定遍历顺序** 从递归公式上可以看出,`dp[i] 依赖于 dp[i-1]`,所以是从前向后遍历。 **Code** 二维 class Solution { public int maxProfit(int[] prices, int fee) { if(prices==null||prices.length==0) return 0; int n = prices.length; int[][] dp = new int[n][2]; dp[0][0] = -prices[0]; dp[0][1] = 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] - fee); } return dp[n-1][1]; } } 一维 class Solution { public int maxProfit(int[] prices, int fee) { if(prices==null||prices.length==0) return 0; int n = prices.length; int[] dp = new int[2]; dp[0] = -prices[0]; dp[1] = 0; for(int i = 1;i < n;i++){ dp[0] = Math.max(dp[0],dp[1] - prices[i]); dp[1] = Math.max(dp[1],dp[0] + prices[i] - fee); } return dp[1]; } } ### 股票问题总结篇 ### ![image-20221217115042848][] **卖股票的最佳时机** 【动态规划】 * `dp[i][0]` 表示第i天持有股票所得现金。 * `dp[i][1]` 表示第i天不持有股票所得现金。 如果第i天持有股票即`dp[i][0]`, 那么可以由两个状态推出来 * 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:`dp[i - 1][0]` * 第i天买入股票,所得现金就是买入今天的股票后所得现金即:-prices\[i\] 所以`dp[i][0] = max(dp[i - 1][0], -prices[i]);` 如果第i天不持有股票即`dp[i][1]`, 也可以由两个状态推出来 * 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:`dp[i - 1][1]` * 第i天卖出股票,所得现金就是按照今天股票佳价格卖出后所得现金即:`prices[i] + dp[i - 1][0] 所以dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);` **Code** class Solution { public int maxProfit(int[] prices) { if(prices==null||prices.length==0){ return 0; } int n = prices.length; int[][] dp = new int[n][2]; dp[0][1] = -prices[0]; dp[0][0] = 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],-prices[i]); } return dp[n - 1][0]; } } **买卖股票的最佳时机II** 【动态规划】 dp数组定义: * `dp[i][0]` 表示第i天持有股票所得现金 * `dp[i][1]` 表示第i天不持有股票所得最多现金 如果第i天持有股票即`dp[i][0]`, 那么可以由两个状态推出来 * 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:`dp[i - 1][0]` * 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:`dp[i - 1][1] - prices[i]` 在[121. 买卖股票的最佳时机][121.]中,因为股票全程只能买卖一次,所以如果买入股票,那么第i天持有股票即`dp[i][0]`一定就是 -prices\[i\]。 而本题\*\*,因为一只股票可以买卖多次\*\*,所以当第i天买入股票的时候,所持有的现金可能有之前买卖过的利润。 **Code** **二维数组** class Solution { public int maxProfit(int[] prices) { if(prices==null||prices.length==0){ return 0; } int n = prices.length; int[][] dp = new int[n][2]; dp[0][1] = -prices[0]; dp[0][0] = 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]; } } **一维数组** // 优化空间 class Solution { public int maxProfit(int[] prices) { int[] dp = new int[2]; dp[1] = -prices[0]; dp[0] = 0; for(int i = 1; i < prices.length; i++){ dp[1] = Math.max(dp[1], dp[0] - prices[i]); dp[0] = Math.max(dp[0], dp[1] + prices[i]); } return dp[0]; } } **买卖股票的最佳时机Ⅲ** 【动态规划】 一天一共就有五个状态, 1. 没有操作 2. 第一次买入 3. 第一次卖出 4. 第二次买入 5. 第二次卖出 `dp[i][j]`中 i表示第i天,j为 \[0 - 4\] 五个状态,`dp[i][j]`表示第i天状态j所剩最大现金。 达到`dp[i][1]`状态,有两个具体操作: * 操作一:第i天买入股票了,那么`dp[i][1] = dp[i-1][0] - prices[i]` * 操作二:第i天没有操作,而是沿用前一天买入的状态,即:`dp[i][1] = dp[i - 1][1]` `dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);` 同理`dp[i][2]`也有两个操作: * 操作一:第i天卖出股票了,那么`dp[i][2] = dp[i - 1][1] + prices[i]` * 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:`dp[i][2] = dp[i - 1][2]` 所以`dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])` 同理可推出剩下状态部分: `dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);` `dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);` **Code** **二维** class Solution { public int maxProfit(int[] prices) { int n = prices.length; if(prices==null||n==0){ return 0; } int[][] dp = new int[n][5]; dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for(int i = 1; i < n; 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[n-1][4]; } } **一维** class Solution { public int maxProfit(int[] prices) { int[] dp = new int[5]; dp[1] = -prices[0]; dp[3] = -prices[0]; for(int i = 1; i < prices.length; i++){ dp[1] = Math.max(dp[1], -prices[i]); dp[2] = Math.max(dp[2], dp[1]+prices[i]); dp[3] = Math.max(dp[3], dp[2]-prices[i]); dp[4] = Math.max(dp[4], dp[3]+ prices[i]); } return dp[4]; } } **买卖股票的最佳时机Ⅳ** 使用二维数组 `dp[i][j]` :第i天的状态为j,所剩下的最大现金是`dp[i][j]` j的状态表示为: * 0 表示不操作 * 1 第一次买入 * 2 第一次卖出 * 3 第二次买入 * 4 第二次卖出 * … **除了0以外,偶数就是卖出,奇数就是买入**。 1. 确定递推公式 达到`dp[i][1]`状态,有两个具体操作: * 操作一:第i天买入股票了,那么`dp[i][1] = dp[i - 1][0] - prices[i]` * 操作二:第i天没有操作,而是沿用前一天买入的状态,即:`dp[i][1] = dp[i - 1][1]` `dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);` 同理`dp[i][2]`也有两个操作: * 操作一:第i天卖出股票了,那么`dp[i][2] = dp[i - 1][1] + prices[i]` * 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:`dp[i][2] = dp[i - 1][2]` `dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])` **Code** **二维**:股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作 class Solution { public int maxProfit(int k, int[] prices) { if(prices==null||prices.length==0){ return 0; } int n = prices.length; int[][] dp = new int[n][2*k+1]; for(int j = 1;j < 2*k; j += 2){ dp[0][j] = -prices[0]; } for(int i = 1;i < n;i++){ for(int j = 0;j < 2*k;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[n - 1][2*k]; } } **一维**(参考) class Solution { public int maxProfit(int k, int[] prices) { if(prices.length == 0){ return 0; } if(k == 0){ return 0; } // 其实就是123题的扩展,123题只用记录2次交易的状态 // 这里记录k次交易的状态就行了 // 每次交易都有买入,卖出两个状态,所以要乘 2 int[] dp = new int[2 * k]; // 按123题解题格式那样,做一个初始化 for(int i = 0; i < dp.length / 2; i++){ dp[i * 2] = -prices[0]; } for(int i = 1; i <= prices.length; i++){ dp[0] = Math.max(dp[0], -prices[i - 1]); dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]); // 还是与123题一样,与123题对照来看 // 就很容易啦 for(int j = 2; j < dp.length; j += 2){ dp[j] = Math.max(dp[j], dp[j - 1] - prices[i-1]); dp[j + 1] = Math.max(dp[j + 1], dp[j] + prices[i - 1]); } } // 返回最后一次交易卖出状态的结果就行了 return dp[dp.length - 1]; } } **最佳买卖股票时机含冷冻期** * `dp[i][j]`,第i天状态为j,所剩的最多现金为`dp[i][j]`。 * 状态一:买入股票状态(今天买入股票,或者是之前就买入了股票然后没有操作)`dp[i][0]` * 卖出股票状态,这里就有两种卖出股票状态 * 状态二:两天前就卖出了股票,度过了冷冻期,一直没操作,今天保持卖出股票状态`dp[i][1]` * 状态三:今天卖出了股票`dp[i][2]` * 状态四:今天为冷冻期状态,但冷冻期状态不可持续,只有一天!`dp[i][3]` **达到买入股票状态(状态一)即:`dp[i`\]\[0\],有两个具体操作:** * 操作一:前一天就是持有股票状态(状态一),`dp[i][0] = dp[i - 1][0]` * 操作二:今天买入了,有两种情况 * 前一天是冷冻期(状态四),`dp[i - 1][3] - prices[i]` * 前一天是保持卖出股票状态(状态二),`dp[i - 1][1] - prices[i]` 所以操作二取最大值,即:`max(dp[i - 1][3], dp[i - 1][1]) - prices[i]` 那么`dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);` 达到保持卖出股票状态(状态二)即:`dp[i][1]`,有两个具体操作: * 操作一:前一天就是状态二 * 操作二:前一天是冷冻期(状态四) `dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])`; 达到今天就卖出股票状态(状态三),即:`dp[i][2]` ,只有一个操作: * 操作一:昨天一定是买入股票状态(状态一),今天卖出 即:`dp[i][2] = dp[i - 1][0] + prices[i]`; 达到冷冻期状态(状态四),即:`dp[i][3]`,只有一个操作: * 操作一:昨天卖出了股票(状态三) `dp[i][3] = dp[i - 1`\]\[2\]; 综上分析,递推代码如下: dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][1] - prices[i],dp[i-1][3] - prices[i])); dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]); dp[i][2] = (dp[i-1][0] + prices[i]); dp[i][3] = (dp[i-1][2]); **Code** class Solution { public int maxProfit(int[] prices) { if(prices==null|prices.length==0) return 0; int n = prices.length; int[][] dp = new int[n][4]; dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0; dp[0][3] = 0; for(int i = 1;i < n;i++){ dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][1] - prices[i],dp[i-1][3] - prices[i])); dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]); dp[i][2] = (dp[i-1][0] + prices[i]); dp[i][3] = (dp[i-1][2]); } return Math.max(dp[n-1][1],Math.max(dp[n-1][2],dp[n-1][3])); } } **买卖股票的最佳时机含手续费** * `dp[i][j]`表示第i天的状态为j,所剩的最多现金 * `dp[i][0]` 表示第i天持有股票所剩最多现金。 `dp[i][1]` 表示第i天不持有股票所得最多现金,如果第i天持有股票即`dp[i][0]`, 那么可以由两个状态推出来 * 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:`dp[i - 1][0]` * 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:`dp[i - 1][1] - prices[i]` 在来看看如果第i天不持有股票即`dp[i][1]`的情况, 依然可以由两个状态推出来 * 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:`dp[i - 1][1]` * 第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金即:`dp[i - 1][0] + prices[i] - fee` 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); **Code** 二维 class Solution { public int maxProfit(int[] prices, int fee) { if(prices==null||prices.length==0) return 0; int n = prices.length; int[][] dp = new int[n][2]; dp[0][0] = -prices[0]; dp[0][1] = 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] - fee); } return dp[n-1][1]; } } 一维 class Solution { public int maxProfit(int[] prices, int fee) { if(prices==null||prices.length==0) return 0; int n = prices.length; int[] dp = new int[2]; dp[0] = -prices[0]; dp[1] = 0; for(int i = 1;i < n;i++){ dp[0] = Math.max(dp[0],dp[1] - prices[i]); dp[1] = Math.max(dp[1],dp[0] + prices[i] - fee); } return dp[1]; } } #### #### [Link 1]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ [Link 2]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ [Link 3]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/ [image-20221212220237134]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/871a21bb52d841d6909d8a20b695b9ee.png [Link 4]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/ [image-20221214195453126]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d76914339e544c1cb80af222f32e085c.png [Link 5]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/ [image-20221217111152412]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/44c5670e744d4f65aaecf4f8743beb89.png [Link 6]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/ [image-20221217115042848]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f7370281541845ef89d2231ab5c7560e.png [121.]: https://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html
相关 Day15——字符串专题 文章目录 33.翻转字符串里的单词 34.实现 \`strStr()\` -------------------- 33.翻 ╰+哭是因爲堅強的太久メ/ 2024年04月01日 09:20/ 0 赞/ 43 阅读
相关 Day38——Dp专题 DP专题 动态规划五部曲: 确定dp数组以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组 1.斐波 怼烎@/ 2024年03月31日 12:42/ 0 赞/ 27 阅读
相关 dp专题题目记录 1.数的划分 2星 [https://ac.nowcoder.com/acm/problem/16695][https_ac.nowcoder.com_acm_prob 青旅半醒/ 2023年08月17日 16:26/ 0 赞/ 92 阅读
还没有评论,来说两句吧...