网站导航做多大,个人品牌打造方案,校园网页制作模板,梵克雅宝是哪个国家的牌子188.买卖股票的最佳时机IV 题目链接#xff1a;188.买卖股票的最佳时机IV 文档讲解#xff1a;代码随想录 状态#xff1a;不会 思路#xff1a; 在股票买卖1使用一维dp的基础上#xff0c;升级成二维的即可。
定义dp[k1][2]#xff0c;其中 dp[j][0] 表示第j次交易后持…188.买卖股票的最佳时机IV 题目链接188.买卖股票的最佳时机IV 文档讲解代码随想录 状态不会 思路 在股票买卖1使用一维dp的基础上升级成二维的即可。
定义dp[k1][2]其中 dp[j][0] 表示第j次交易后持有股票的最大利润dp[j][1] 表示第j次交易后不持有股票的最大利润。初始化时对所有持有股票的情况要变成dp[i][0] -prices[0];
题解 要注意 dp[j][0] Math.max(dp[j][0], dp[j - 1][1] - prices[i]); dp[j - 1][1] - prices[i] 是因为买入股票的操作要用dp[j-1][1],也就是上次卖出去得到的钱来买这次的股票 public int maxProfit(int k, int[] prices) {// 特殊情况处理如果价格数组为空或只有一个元素返回0if (prices.length 0) return 0;// dp数组定义为k1行2列// dp[j][0] 表示第j次交易后持有股票的最大利润// dp[j][1] 表示第j次交易后不持有股票的最大利润int[][] dp new int[k 1][2];// 初始化第1到第k次交易后的持有股票的最大利润为 -prices[0]for (int i 1; i k; i) {dp[i][0] -prices[0];}// 遍历每一天的股票价格for (int i 1; i prices.length; i) {// 倒序遍历每一次交易,也可以正序,但是倒序更快一点for (int j k; j 1; j--) {// 更新第j次交易后不持有股票的最大利润dp[j][1] Math.max(dp[j][1], dp[j][0] prices[i]);// 更新第j次交易后持有股票的最大利润// dp[j - 1][1] - prices[i] 是因为买入股票的操作要用dp[j-1][1],也就是上次卖出去得到的钱来买这次的股票dp[j][0] Math.max(dp[j][0], dp[j - 1][1] - prices[i]);}}// 返回最多k次交易后不持有股票的最大利润return dp[k][1];}309.最佳买卖股票时机含冷冻期 题目链接309.最佳买卖股票时机含冷冻期 文档讲解代码随想录 状态不会 思路
第i天的最大收益由持有和不持有股票两种状态推导出来考虑到由冷冻期那么第i天持有股票可以考虑跳过昨天从前天推导。
假设有今天持股情况下的最大收益 dp[i][0]、昨天不持股的最大收益 dp[i−1][0]、昨天持股的最大收益 dp[i−1][0]、前天不持股的最大收益 dp[i−2][1]前天持股的最大收益 dp[i−2][0]。先将目光集中在前天分别考虑前天持股与不持股的情况试试能不能推导出今天的最大收益。
对于 dp[i−2][0] 来说它表示前天结束时手中还有股票那么如果昨天选择将前天的股票卖掉由于冷冻期的存在今天是不能交易的自然今天手中也不可能还有股票推导不出 dp[i][0]因此这种情况可以直接忽略如果前天选择保留股票到昨天昨天也只能继续保留股票才能让今天手中也有股票这时 dp[i][0]dp[i−1][0]这种情况已经在上面的状态转移方程中考虑到了因此也不用担心。 对于 dp[i−2][1] 来说它表示前天结束时手中没有股票如果昨天买入股票只能是将股票保留到今天才能推出 dp[i][0]这时 dp[i]dp[i−1][0] 在状态转移方程中已经考虑到了如果昨天不买入股票那么由于昨天手中没有股票只能是今天买入同时因为昨天没交易昨天的最大收益和前天相同 dp[i−1][1]dp[i−2][1]所以这种情况的最大收益是 dp[i−2][1]−prices[i]。
题解 public int maxProfit(int[] prices) {int n prices.length;// 如果价格数组长度为0直接返回0if (n 0) {return 0;}// 定义一个二维数组 dpdp[i][0] 表示第 i 天持有股票的最大利润// dp[i][1] 表示第 i 天不持有股票的最大利润int[][] dp new int[n 1][2];// 初始化第一天的状态dp[1][0] -prices[0]; // 第一天持有股票利润为负的当前股票价格// 从第二天开始遍历价格数组for (int i 2; i n; i) {// 第 i 天持有股票的最大利润可以选择前一天也持有股票或者前两天不持有股票今天买入dp[i][0] Math.max(dp[i - 1][0], dp[i - 2][1] - prices[i - 1]);// 第 i 天不持有股票的最大利润可以选择前一天也不持有股票或者前一天持有股票今天卖出dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i - 1]);}// 返回倒数第二天不持有股票的最大利润return dp[n][1]; // 因为是倒数第二天所以这里改为 dp[n][1]}714.买卖股票的最佳时机含手续费 题目链接714.买卖股票的最佳时机含手续费 文档讲解代码随想录 状态终于做出来一道了。。。。 思路和股票买卖第2道题一样不过每次卖出的时候扣除手续费就好了。
题解
public int maxProfit(int[] prices, int fee) {if (prices.length 1) {return 0;}int hasStock -prices[0]; // 第一天买入股票后的收益int noStock 0; // 第一天不买股票的收益for (int i 1; i prices.length; i) {// 今天选择买入股票或者保持昨天持有股票的状态hasStock Math.max(hasStock, noStock - prices[i]);// 今天选择卖出股票或者保持昨天没有股票的状态noStock Math.max(noStock, hasStock prices[i] - fee);}return noStock; // 最后一天不持有股票的最大收益
}
