代码随想录算法第四十一天| LeetCode121买卖股票的最佳时机、LeetCode122买卖股票的最佳时机Ⅱ、LeetCode123买卖股票的最佳时机Ⅲ

LeetCode 121 买卖股票的最佳时机

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

文档讲解：代码随想录

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

思路与感想：题目的难点在于不知道dp数组的含义怎么设置，当时只想着用一个一维的dp数组表示第i天，却没去从每一天的状态入手，我估摸着即便我想到用二维dp数组表示的话，也大概率是想着0和1表示第i天卖出或买入的行为，而不会想着第i天持有或者不持有这个股票的状态，后者的高明之处在于它让每天与前一天后一天都产生了联系，由此可以思考出递推关系。但是前者光定义每一天的行为，那相当于每一天都是独立的，因为每天都有可能进行买入卖出股票，自然也联系不到一起了。另一个巧妙地地方在于把现金初始化0，相当于买入股票地时候其实是在赊账，这一点也让后续地递推计算方便了很多。

收获：1.股票问题DP数组的设置

class Solution { public int maxProfit(int[] prices) { int[][] dp = new int[prices.length][2]; // 确定dp数组下标含义，dp[i][0]表示第i天不持有股票的最大money数，dp[i][1]表示第天持有股票的最大money数 dp[0][0] = 0; // 第1天不持有股票说明现金还是0 dp[0][1] -= prices[0]; // 第1天持有股票说明就是在第1天买的现金为-prices[0] for (int i = 1; i < prices.length; i++) { // 从左往右递推 dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i]); // 第i天不持有股票有两种情况，第一种是第i-1天也不持有股票，即dp[i - 1][0]，第二种是第i-1天还持有股票，第i天就卖出取了，即dp[i - 1][1] + prices[i]，两个值求最大 dp[i][1] = Math.max(dp[i - 1][1],-prices[i]); // 第i天持有股票也有两种情况，第一种是第i-1天就持有股票了，即dp[i - 1][1]，第二种是第i天才买股票，即0 - prices[i]，两个值求最大 } return dp[prices.length - 1][0]; // 求最后一天不持有股票的现金数量(肯定比持有股票的现金数多) } }

LeetCode 122 买卖股票的最佳时机 Ⅱ

题目链接：122.买卖股票的最佳时机 Ⅱ

文档讲解：代码随想录

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

思路与感想：这道题目上一题唯一的区别就在于可以多次买卖，这一点在上述代码中其实就只有递推dp[i][1]的时候其中一种情况需要改动，正因为可以多次买卖，所以在第i天购入股票的时候，现金可能不为0，因为在此之前可能已经经过多番买卖了，所以应该用dp[i - 1][0]减去prices[i]才行。

收获：1.多次买卖与买卖一次递推公式的区别

class Solution { public int maxProfit(int[] prices) { int[][] dp = new int[prices.length][2]; dp[0][0] = 0; dp[0][1] -= prices[0]; for (int i = 1; i < prices.length; 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]); // 区别在于递推dp[i][1]时，如果前一天没持有股票而是第i天才购入的，由于可以多次买卖，所以前面可能已经进行过多番交易了，此时现金不是0而应该时dp[i - 1][0]，然后减去第i天的price才是当天持有股票的现金的一种情况 } return dp[prices.length - 1][0]; } }

LeetCode 123 买卖股票的最佳时机 Ⅲ

题目链接：123.买卖股票的最佳时机 Ⅲ

文档讲解：代码随想录

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

思路与感想：刚写这道题目的时候想着如果不能够多次买卖的话，那就需要在递推的时候限定购买次数，起初想着是用回溯加动态规划但是发现这样的话那还是跟直接回溯没啥区别，肯定会超时，后面像这样增加DP数组维度用以记录是第几次交易，后面发现如果泛泛记录交易次数是无法确定递推的时候是加上还是减去对应股票值得，就又想着增加一个维度记录是买入还是卖出，觉得挺麻烦感觉应该不是这样做的，后面看完卡哥思路才发现这样做其实也可以做出来只是维度搞复杂了，只需要两个维度即可，只不过用01234表示不同操作状态而已，没必要新增维度。后面递推的话也是两种情况，一种延续前一天状态，一种在当天发生操作，求最大值。最后返回第二次卖出股票的值，一定是最大值，因为它包含了第一次卖出股票的值，如果第一次卖出的股票已经是最大值了，那第二次顶多在当天买入又卖出，值是一样的。

收获：1.状态增加时不仅要想着增加维度，还要想能不能在既有维度上表示新增的状态

class Solution { public int maxProfit(int[] prices) { int[][] dp = new int[prices.length][5];// dp[i][0]表示不操作，dp[i][1]表示第一次持有，dp[i][2]表示第一次不持有，dp[i][3]表示第二次持有，dp[i][4]表示第二次不持有 dp[0][1] -= prices[0]; // 初始现金为0，第一次持有减去对应值 dp[0][3] -= prices[0]; // 第一次不持有后现金为0，即dp[0][2] = 0，在此基础上又第二次持有股票，减去对应值，相当于同一天买入卖出又买入又卖出，最终现金还是0 for (int i = 1; i < prices.length; 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[prices.length - 1][4]; } }

今天早起把买卖股票的三道题目写完了，难度都一般，花了四个小时不到，理解起来特别容易，很快就写完了，今天没课，上一周忙于pre和做ppt还有六级的事情，导致框架一点没学，这周重启springboot和vue框架，主要是基于springboot和vue框架做前后端分离开发Web，之前学Web已经是一个多月前了，有点遗忘，当时做了个管理系统，希望这次能再多多熟悉Web的开发流程。还有英语口语和日语的学习也要慢慢捡起来了，现在的算法强度慢慢适应花的时间更少了，就要寻找更多能进行价值产出的学习了。