188. 买卖股票的最佳时机 iv
给定一个整数数组prices，其中prices[i]是给定股票第i天的价格，以及一个整数k。
找到你能获得的最大利润。您最多可以完成k次交易：即您最多可以买入k次，最多可以卖出k次。
注意：您不能同时进行多项交易（即您必须先卖出股票才能再次购买）。
示例1：
输入：k = 2，价格 = [2,4,1]
输出：2
说明：第 1 天买入（价格 = 2），第 2 天卖出（价格 = 4），利润 = 4-2 = 2。
示例2：
输入：k = 2，价格 = [3,2,6,5,0,3]
输出：7
解释：第 2 天买入（价格 = 2）并在第 3 天卖出（价格 = 6），利润 = 6-2 = 4。然后在第 5 天买入（价格 = 0）并在第 6 天卖出（价格 = 3） ，利润=3-0=3.
限制：
萌动AI
CreateAI旗下AI动漫视频生成平台
438 查看详情
1 <=k <=100
1 <=prices.length <=1000
0 <= 价格[i] <= 1000
原始页面
public int maxprofit(int k, int[] prices) { /**[0][0] do nothing in day 0 [0][1] own the stock for 1st time in day 0 [0][2] not own the stock for 1st time in day 0 [0][3] own the stock for 2nd time in day 0 [0][4] not own the stock for 2nd time in day 0 .... [0][k*2-1] own the stock for kth time in day 0 [0][k*2] not own the stock for kth time in day 0 [1][1] = max([0][1],[0][0]-prices[1]) [1][2] = max([0][2],[0][1]+prices[1]) [1][3] = max([0][3],[0][2]-prices[1]) [i][j] if j is odd means we need to pay for the stock or keep the own status if j is even means we can sell the stock or keep the non-stock status */ int[][] dp = new int[prices.length+1][k*2+1]; for(int i=1; i<=k*2; i+=2){ dp[0][i] = -prices[0]; } for(int i=1; i<prices.length; i++){ for(int j=1; j<=k*2; j++){ dp[i][j] = math.max( dp[i-1][j], dp[i-1][j-1] + ((j % 2 == 0) ? 1 : -1) * prices[i] ); } } return dp[prices.length-1][k*2]; }
309. 买卖股票的最佳时机（有冷却时间）
给你一个数组价格，其中prices[i]是给定股票在第i天的价格。
找到你能获得的最大利润。您可以根据需要完成任意多次交易（即多次买入一股股票并卖出一股股票），但有以下限制：
卖出股票后，第二天（即冷却一天）将无法再购买股票。
注意：您不能同时进行多项交易（即您必须先卖出股票才能再次购买）。
示例1：
输入：价格 = [1,2,3,0,2]
输出：3
说明：交易 = [买入、卖出、冷却、买入、卖出]
示例2：
输入：价格 = [1]
输出：0
限制：
1 <=prices.length <=5000
0 <= 价格[i] <= 1000
public int maxprofit(int[] prices) { /** [0] own the stock [1] colldown [2] not own the stock */ int[][] dp = new int[prices.length][3]; dp[0][0] = -prices[0]; for(int i=1; i<prices.length; i++){ dp[i][0] = math.max(dp[i-1][0], dp[i-1][2]-prices[i]); dp[i][1] = dp[i-1][0] + prices[i]; dp[i][2] = math.max(dp[i-1][1], dp[i-1][2]); } // arrays.stream(dp).map(arrays::tostring).foreach(system.out::println); return math.max(dp[prices.length-1][2],dp[prices.length-1][1]); }
请注意，当冷却期时，我们无法购买新股票。
在此回归关系中，它显示 dp[2] 是我们更新的最后一个，以便我们可以继续覆盖冷却条件。
714. 买卖股票并收取交易费的最佳时机
给你一个价格数组，其中prices[i]是给定股票第i天的价格，以及代表交易费用的整数费用。
找到你能获得的最大利润。您可以完成任意数量的交易，但您需要为每笔交易支付交易费用。
注意：
您不得同时进行多项交易（即，您必须先卖出股票才能再次购买）。
每次买卖股票只收取一次交易费。
示例1：
输入：价格 = [1,3,2,8,4,9]，费用 = 2
输出：8
说明：最大利润可以通过以下方式实现：
以价格[0] = 1 购买以价格[3] = 8 出售以价格[4] = 4 购买以价格[5] = 9 出售总利润为 ((8 – 1) – 2) + ((9 – 4) – 2) = 8。示例2：
输入：价格 = [1,3,7,5,10,3]，费用 = 3
输出：6
限制：
1 <= 价格.长度 <= 5 * 10^4
1 <= 价格[i] < 5 * 10^4
0 <= 费用 < 5 * 10^4
原始页面
我们唯一应该考虑的就是增加交易费，但是费用并不会改变我们之前的逻辑
public int maxProfit(int[] prices, int fee) { int[] dp = new int[2]; int temp = 0; dp[0] = -prices[0]; for(int i=1; i<prices.length; i++){ temp = dp[1]; dp[1] = Math.max(dp[1], dp[0] + prices[i] -fee); dp[0] = Math.max(dp[0], temp-prices[i]); } return dp[1]; }
以上就是LeetCode Day 动态规划第 9 部分的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/511876.html
微信扫一扫 
支付宝扫一扫 
