PHP amp MySQL网站建设宝典服装东莞网站建设

PHP amp MySQL网站建设宝典,服装东莞网站建设,外贸网站建设公司信息,我国网站建设现状LeetCode 121 买卖股票的最佳时机 题目链接#xff1a;121.买卖股票的最佳时机 文档讲解#xff1a;代码随想录 视频讲解#xff1a;买卖股票的最佳时机 思路与感想#xff1a;题目的难点在于不知道dp数组的含义怎么设置#xff0c;当时只想着用一个一维的dp数组表示第i天…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的开发流程。还有英语口语和日语的学习也要慢慢捡起来了现在的算法强度慢慢适应花的时间更少了就要寻找更多能进行价值产出的学习了。