网站ftp文件,wordpress 评论框 模板,interiart wordpress,门户网站是啥文章目录 前言一、309.最佳买卖股票时机含冷冻期二、714.买卖股票的最佳时机含手续费总结 前言
买卖股票 完结#xff1b; 一、309.最佳买卖股票时机含冷冻期 确定dp数组以及下标的含义 dp[i][j]#xff0c;第i天状态为j#xff0c;所剩的最多现金为dp[i][j]。 其实本题很多… 文章目录 前言一、309.最佳买卖股票时机含冷冻期二、714.买卖股票的最佳时机含手续费总结 前言
买卖股票 完结 一、309.最佳买卖股票时机含冷冻期 确定dp数组以及下标的含义 dp[i][j]第i天状态为j所剩的最多现金为dp[i][j]。 其实本题很多同学搞的比较懵是因为出现冷冻期之后状态其实是比较复杂度 具体可以区分出如下四个状态 状态一持有股票状态今天买入股票或者是之前就买入了股票然后没有操作一直持有不持有股票状态这里就有两种卖出股票状态 状态二保持卖出股票的状态两天前就卖出了股票度过一天冷冻期。或者是前一天就是卖出股票状态一直没操作状态三今天卖出股票状态四今天为冷冻期状态但冷冻期状态不可持续只有一天 注意这里的每一个状态例如状态一是持有股票股票状态并不是说今天一定就买入股票而是说保持买入股票的状态即可能是前几天买入的之后一直没操作所以保持买入股票的状态。 确定递推公式 达到买入股票状态状态一即dp[i][0]有两个具体操作 操作一前一天就是持有股票状态状态一dp[i][0] dp[i - 1][0]操作二今天买入了有两种情况 前一天是冷冻期状态四dp[i - 1][3] - prices[i]前一天是保持卖出股票的状态状态二dp[i - 1][1] - prices[i] 那么dp[i][0] max(dp[i - 1][0], dp[i - 1][3] - prices[i], 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数组如何初始化 这里主要讨论一下第0天如何初始化。 如果是持有股票状态状态一那么dp[0][0] -prices[0]一定是当天买入股票。 保持卖出股票状态状态二这里其实从 「状态二」的定义来说 很难明确应该初始多少这种情况我们就看递推公式需要我们给他初始成什么数值。 如果i为1第1天买入股票那么递归公式中需要计算 dp[i - 1][1] - prices[i] 即 dp[0][1] - prices[1]那么大家感受一下 dp[0][1] 即第0天的状态二应该初始成多少只能初始为0。想一想如果初始为其他数值是我们第1天买入股票后 手里还剩的现金数量是不是就不对了。 今天卖出了股票状态三同上分析dp[0][2]初始化为0dp[0][3]也初始为0。 确定遍历顺序 从递归公式上可以看出dp[i] 依赖于 dp[i-1]所以是从前向后遍历。 举例推导dp数组 代码
class Solution {public int maxProfit(int[] prices) {if(prices null || prices.length 2){return 0;}int[][] dp new int[prices.length][4];//持有股票 前一天也持有卖出后买入冷冻期后买入//保持卖出股票 前一天卖出了 前一天是冷冻期//今天卖出股票 买入后卖出//冷冻期dp[0][0] -prices[0];for(int i 1;iprices.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]));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[prices.length-1][1],Math.max(dp[prices.length-1][2],dp[prices.length-1][3]));}
} 二、714.买卖股票的最佳时机含手续费 这里重申一下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] 所以dp[i][0] max(dp[i - 1][0], 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][1] max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee); class Solution {public int maxProfit(int[] prices, int fee) {int len prices.length;int[][] dp new int[len][2];dp[0][0] -prices[0];for(int i1;ilen;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[len-1][1];// return Math.max(dp[len-1][0],dp[len-1][1]);}
} 总结 从买卖一次到买卖多次从最多买卖两次到最多买卖k次从冷冻期再到手续费最后再来一个股票大总结可以说对股票系列完美收官了。
