代码随想录算法第四十二天| LeetCode188买卖股票的最佳时机Ⅳ、LeetCode309最佳买卖股票时机含冷冻期、LeetCode714买卖股票的最佳时机含手续费

LeetCode 188 买卖股票的最佳时机 Ⅳ

题目链接：188.买卖股票的最佳时机 Ⅳ

文档讲解：代码随想录

视频讲解：买卖股票的最佳时机 Ⅳ

思路与感想：这道题目虽然是道hard但是在做过了股票系列Ⅲ后立马就有思路直接秒了，跟Ⅲ的唯一区别就在于它有k次交易而非已知的两次了，在代码上体现的差异点就是，k次交易说明有2k + 1种操作状态，那在递推每一天的dp值得时候其实要求2k次（dp[i][0]不用算默认为0），再者自己去定义除了0之外奇数是购入，偶数是卖出，那很自然地就会想到在初始化和遍历每一天的时候都加一个for循环进行初始化或者递推，因为购入和卖出的递推公式是不一样的。卡哥在遍历时也选择i+=2处理，并没有像我一样一个个判断奇数偶数，而是一次交易看作一个整体内部直接dp[i][j + 1]和dp[i][j + 2]。

收获：1.for循环内置批量处理多种状态

// 动态规划 class Solution { public int maxProfit(int k, int[] prices) { int[][] dp = new int[prices.length][2 * k + 1]; // k次交易说明有2k + 1种操作情况 for (int i = 1; i < 2 * k + 1; i += 2) { dp[0][i] -= prices[0]; // 奇数买入股票偶数卖出进行dp数组初始化 } for (int i = 1; i < prices.length; i++) { // 外层遍历第几天 for (int j = 1; j < 2 * k + 1; j++) { // 内层遍历当天所有操作情况递推每种情况的dp值 if (j % 2 != 0) { dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - 1] - prices[i]); // 奇数购入股票，两种情况，延续前一天同一个操作，或者当天购入 } else { dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - 1] + prices[i]); // 偶数卖出股票，同上 } } } return dp[prices.length - 1][2 * k]; } }

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

题目链接：309.买卖股票的最佳时机含冷冻期

文档讲解：代码随想录

视频讲解：买卖股票的最佳时机含冷冻期

思路与感想：这道题目的状态挺难想的，持有股票，不持有股票，当天卖出股票，冷冻期。回过头来再看的话，持股与不持股或许可以延续前面的题目想到这么设置状态，然后题目多了个冷冻期那势必也要给冷冻期设置一个状态，然后在你想着如何对冷冻期的DP值进行递推的时候，自然会想到利用它前一天正好卖出股票来实现，但是现在只有不持股这个摸棱两可的状态，所有你不得不从不持股里面抽出来一种当天卖出股票的状态，那另一种状态就是保持卖出股票的状态，这样才可以递推冷冻期状态。当然这都是事后诸葛亮了，四种状态不仅难想，而且即便想出来了，可能递推公式也不一定写对。而且通过这道题我发现了DP类型题目的状态不是唯一的，不同题解可能有不同的设置，最重要的是自洽。另外在初始化的时候dp[0][1]、dp[0][2]还有dp[0][3]明显根据题意是个非法dp值，所以这个时候不能死扣定义而是要回归到递推公式上，找一个近一点的状态递推，看看要初始化成什么值才能让递推符合提议逻辑。这样就知道要把他们都初始化成0，这样才会让第0天之后的日子现金数正常。

收获：1.多思考状态，想全状态的同时考虑每个状态之间能不能递推出来，不能的话能不能通过从原有状态中抽取状态实现递推连接；2.初始化遇到非法dp值从递推公式下手

class Solution { public int maxProfit(int[] prices) { int[][] dp = new int[prices.length][4]; // DP数组第二维下标含义：0 持有股票的状态。1 不持有股票的状态。2 当天卖出股票的状态。3冷冻期状态 dp[0][0] -= prices[0]; // 初始化第0天持有股票，即当天买入股票。 注：之所以多设置一个当天卖出股票的状态，是因为冷冻期前一天一定是当天卖出股票，多了冷冻期就要多一个当天卖出，否则光一个不持有股票就笼统了推不出冷冻期的DP值 for (int i = 1; i < prices.length; i++) { dp[i][0] = Math.max(dp[i - 1][0],Math.max(dp[i - 1][1] - prices[i],dp[i - 1][3] - prices[i])); // 持有股票 三种情况：1.延续前一天的持有 2.前一天不持有当天买入 3.前一天冷冻当天买入 dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][3]); // 不持有股票 两种情况：1.延续前一天不持有 2.前一天冷冻期 dp[i][2] = dp[i - 1][0] + prices[i]; // 当天卖出 一种情况：前一天肯定持有股票 dp[i][3] = dp[i - 1][2]; // 冷冻期 一种情况：前一天肯定卖出股票 } return Math.max(dp[prices.length - 1][1],Math.max(dp[prices.length - 1][2],dp[prices.length - 1][3])); } }

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

题目链接：714.买卖股票的最佳时机含手续费

文档讲解：代码随想录

视频讲解：买卖股票的最佳时机含手续费

思路与感想：题目跟之前的Ⅱ除了要手续费外基本上一模一样的代码，就是在出售股票的时候减去手续费就行了没什么难度。

收获：1.重温持有不持有两种状态

class Solution { public int maxProfit(int[] prices, int fee) { int[][] dp = new int[prices.length][2]; // 两种状态，持有或者不持有股票 dp[0][1] -= prices[0]; // 初始化第0天持有股票的资金数 for (int i = 1; i < prices.length; i++) { dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee); // 两种情况，第一种继承前一天不持有状态，第二种当天卖出股票，需要手续费 dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]); // 同上 } return dp[dp.length - 1][0]; } }

今天算法还算轻松花了三个小时多一点，第一题和第三题都跟前面的股票系列很像所以两个一下子就秒掉了，第二题状态很多，而且很难想不过收获也是最大的。今天把基于vue框架的前端工程化开发看了下，了解了各种Element的使用、Axios的实现，明天就可以开springboot了，打算这块学完把外卖点评顺手敲了。