网站建设培训费用,应用公园下载,企业建设网站注意事项,品牌广告语文章目录前言一、买卖股票的最佳时机III#xff08;力扣123#xff09;二、买卖股票的最佳时机IV#xff08;力扣188#xff09;三、最佳买卖股票时机含冷冻期#xff08;力扣309#xff09;四、买卖股票的最佳时机含手续费#xff08;力扣714#xff09;股票买卖问题总…
文章目录前言一、买卖股票的最佳时机III力扣123二、买卖股票的最佳时机IV力扣188三、最佳买卖股票时机含冷冻期力扣309四、买卖股票的最佳时机含手续费力扣714股票买卖问题总结前言
1、买卖股票的最佳时机III 2、买卖股票的最佳时机IV 3、最佳买卖股票时机含冷冻期 4、买卖股票的最佳时机含手续费 一、买卖股票的最佳时机III力扣123
给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 8888 分析 与之前的区别在于最多可以买卖两次 动规五部曲 1、dp[]数组以及下标含义 dp[i][0]不操作 dp[i][1]第一次持有 dp[i][2]第一次不持有 dp[i][3]第二次持有 dp[i][4]第二次不持有 2、递推公式 dp[i][0] dp[i-1][0] dp[i][1] Math.max(dp[i-1][1],-price[i]) dp[i][2] Math.max(dp[i-1][2],dp[i-1][1]price[i]) dp[i][3] Math.max(dp[i-1][3],dp[i-1][2]-price[i]) dp[i][4] Math.max(dp[i-1][4],dp[i-1][3]price[i]) 3、初始化 dp[0][0] 0; dp[0][1] -price[0]; dp[0][2] 0; dp[0][3] -price[0]; dp[0][4] 0; 4、遍历顺序 从前向后遍历因为dp[i]依靠dp[i - 1]的数值。
二维dp数组
class Solution {public int maxProfit(int[] prices) {int[][] dp new int[prices.length][5];dp[0][0] 0;dp[0][1] -prices[0];dp[0][2] 0;dp[0][3] -prices[0];dp[0][4] 0;for(int i1;iprices.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];}
}优化版滚动数组
class Solution {public int maxProfit(int[] prices) {int[] dp new int[5];dp[0] 0;dp[1] -prices[0];dp[2] 0;dp[3] -prices[0];dp[4] 0;for(int i1;iprices.length;i){dp[1] Math.max(dp[1],-prices[i]);dp[2] Math.max(dp[2],dp[1]prices[i]);dp[3] Math.max(dp[3],dp[2]-prices[i]);dp[4] Math.max(dp[4],dp[3]prices[i]);}return dp[4];}
}二、买卖股票的最佳时机IV力扣188
给定一个整数数组 prices 它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 分析 与之前的区别在于最多可以买卖k次 根据上一题所表现出来的规律 1、dp[]数组以及下标含义 dp[i][0]不操作 dp[i][1]第一次持有 dp[i][2]第一次不持有 dp[i][3]第二次持有 dp[i][4]第二次不持有 …… 当有k次买卖时奇数表示买入偶数表示卖出。 初始化
for(int j0;j2*k1;j){if(j%21){dp[0][j] -prices[0];}
}递推公式 dp[i][0] dp[i-1][0] dp[i][1] Math.max(dp[i-1][1],-price[i]) dp[i][2] Math.max(dp[i-1][2],dp[i-1][1]price[i]) dp[i][3] Math.max(dp[i-1][3],dp[i-1][2]-price[i]) dp[i][4] Math.max(dp[i-1][4],dp[i-1][3]price[i])
for(int i 1; iprices.length; i){for(int j1; j2*k1;jj2){dp[i][j] Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);dp[i][j1] Math.max(dp[i-1][j1],dp[i-1][j]prices[i]);}
}class Solution {public int maxProfit(int k, int[] prices) {int[][] dp new int[prices.length][2*k1];for(int j1;j2*k1;j){if(j%21) dp[0][j] -prices[0];}for(int i1;iprices.length;i){for(int j0;j2*k-1;jj2){dp[i][j1] Math.max(dp[i-1][j1],dp[i-1][j]-prices[i]);dp[i][j2] Math.max(dp[i-1][j2],dp[i-1][j1]prices[i]);}}return dp[prices.length-1][2*k];}
}三、最佳买卖股票时机含冷冻期力扣309
给定一个整数数组其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:
你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。 动规五部曲 1、dp[]数组以及下标含义 dp[i][0]持有股票的状态 dp[i][1]保持卖出股票的状态 dp[i][2]卖出股票状态 dp[i][3]冷冻期
为什么要把 不持有股票状态拆分为两个部分【保持卖出股票的状态、卖出股票状态】因为有冷冻期。必须前一天是卖出股票的状态那么下一天才能是冷冻期
2、递推公式 持有股票状态 1、i-1天就持有dp[i][0] dp[i-1][0]; 2、冷冻期之后买入股票dp[i][0] dp[i-1][3] - prices[i]; 3、冷冻期之后一直没有操作一直都是保持卖出股票状态直到第i天买入dp[i][0] dp[i-1][1] - prices[i]; 因此dp[i][0] Math.max(dp[i-1][0], dp[i-1][3] - prices[i], dp[i][0] dp[i-1][1] - prices[i])
保持卖出股票状态 1、前一天就是保持卖出股票的状态dp[i][1] dp[i-1][1]; 2、前一天是冷冻期dp[i][1] dp[i-1][3] 因此dp[i][1] Math.max(dp[i-1][1] , dp[i-1][3])
卖出股票状态 1、前i-1天持有股票状态第i天卖出股票.dp[i][2] dp[i-1][0]prices[i]; 因此dp[i][2]dp[i-1][0]prices[i];
冷冻期状态 1、前一天卖出股票状态第i天就是冷冻期 dp[i][3] dp[i-1][2] 因此dp[i][3] dp[i-1][2];
3、初始化 dp[0][0] -prices[0]; dp[0][1] 在dp[i][0] Math.max(dp[i-1][0], dp[i-1][3] - prices[i], dp[i][0] dp[i-1][1] - prices[i]) 这个状态下会用到假设i1带入之后 dp[1][0] max(dp[0][0],dp[0][3]-prices[1], dp[0][1]-prices[1]); dp[0][1] 0;
dp[0][2] 0; dp[0][3] 0;
4、遍历顺序 从前向后遍历因为dp[i]依靠dp[i - 1]的数值。
class Solution {public int maxProfit(int[] prices) {int[][] dp new int[prices.length][4];//初始化dp[0][0] -prices[0];dp[0][1] 0;dp[0][2] 0;dp[0][3] 0;//遍历for(int i1;iprices.length;i){//持有股票的状态dp[i][0] Math.max(Math.max(dp[i-1][0],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(Math.max(dp[prices.length-1][3],dp[prices.length-1][2]),dp[prices.length-1][1]);}
}四、买卖股票的最佳时机含手续费力扣714
给定一个整数数组 prices其中 prices[i]表示第 i 天的股票价格 整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易但是你每笔交易都需要付手续费。如果你已经购买了一个股票在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意这里的一笔交易指买入持有并卖出股票的整个过程每笔交易你只需要为支付一次手续费。 在之前有用贪心算法进行求解 贪心算法求解
分析 买卖股票的最佳时机II 可以进行多次买卖但多了手续费
dp[i][0]表示第i天持有股票所得现金。 dp[i][1]表示第i天不持有股票所得最多现金 dp[i][0] max(dp[i-1][0],dp[i-1][1]-prices[i]-fee) dp[i][1] max(dp[i-1][1],dp[i-1][0]prices[i]);
class Solution {public int maxProfit(int[] prices, int fee) {int[][] dp new int[prices.length][2];dp[0][0] -prices[0]-fee;for(int i1;iprices.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[prices.length-1][1];}
}优化后一维滚动数组
class Solution {public int maxProfit(int[] prices, int fee) {int[] dp new int[2];dp[0] -prices[0]-fee;for(int i1;iprices.length;i){dp[0] Math.max(dp[0],dp[1]-prices[i]-fee);dp[1] Math.max(dp[1],dp[0]prices[i]);}return dp[1];}
}股票买卖问题总结 买卖股票的最佳时机力扣121 只能买卖一次 dp[i][0]:持有股票的状态 dp[i][1]:不持有股票的状态 dp[0][0] -prices[0]; dp[0][1] 0; dp[i][0] max(dp[i-1][0], -prices[i]) dp[i][1] max(dp[i-1][1] , dp[i-1][0]prices[i]) 买卖股票的最佳时机||力扣122可以买卖多次 dp[i][0]:持有股票的状态 dp[i][1]:不持有股票的状态 dp[0][0] -prices[0]; dp[0][1] 0; dp[i][0] max(dp[i-1][0], dp[i-1][1]-prices[i]) dp[i][1] max(dp[i-1][1] , dp[i-1][0]prices[i]) 细微变化在于持有股票状态的递推过程 买卖股票的最佳时机|||力扣123最多买卖2次 dp[i][0] 不操作 dp[i][1]:第一次持有股票状态 dp[i][2]:第一次不持有股票状态 dp[i][3]:第二次持有股票状态 dp[i][4]:第二次不持有股票状态 初始化 dp[0][0] 0 dp[0][1] -prices[0]; dp[0][2] 0; dp[0][3] -prices[0]; dp[i][0] dp[i-1][0] dp[i][1] max(dp[i-1][1],-prices[i]) dp[i][2] max(dp[i-1][2], dp[i-1][1]prices[i]) dp[i][3] max(dp[i-1][3], dp[i-1][2]-prices[i]) dp[i][4] max(dp[i-1][4], dp[i-1][3]prices[i]) 买卖股票的最佳时机IV力扣188 最多买卖k次 dp[i][0] 不操作 dp[i][1]:第一次持有股票状态 dp[i][2]:第一次不持有股票状态 dp[i][3]:第二次持有股票状态 dp[i][4]:第二次不持有股票状态 …… 0 ----- 2*k 奇数是持有股票状态 偶数是卖出股票状态 初始化时 if(j%21) dp[0][j] -prices[0]; 奇数时dp[i][j] max(dp[i-1][j],dp[i-1][j-1] - prices[i]) 偶数时dp[i][j1] max(dp[i-1][j1], dp[i-1][j] prices[i]) 最佳买卖股票时机含冷冻期力扣309 买卖多次卖出后有一天是冷冻期 dp[i][0]:持有股票的状态 dp[i][1]:保持卖出股票的状态 dp[i][2]:卖出股票的状态 dp[i][3]:冷冻期 初始化 dp[0][0] -prices[0]; dp[i][0] max(dp[i-1][0], dp[i-1][1]-prices[i], dp[i-1][3]- prices[i]) dp[i][1] 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] 买卖股票的最佳时机含手续费力扣714买卖多次每次都有手续费 dp[i][0]:持有股票的状态 dp[i][1]:不持有股票的状态 dp[0][0] -prices[0]-fee; dp[0][1] 0; dp[i][0] max(dp[i-1][0], dp[i-1][1]-prices[i]-fee) dp[i][1] max(dp[i-1][1] , dp[i-1][0]prices[i]) 细微变化在于多减去手续费
