北京网站设计公司地址,免费营销型wordpress模板下载,深圳大型网站建设服务,网站建设电子商务leetcode 123 买卖股票的最佳时机 III
题目链接
123. 买卖股票的最佳时机 III - 力扣#xff08;LeetCode#xff09;
做题过程
这里有两次交易机会。因此有5种状态。0没有操作#xff0c;1第一次买入#xff0c;2第一次卖出#xff0c;3第二次买入#xff0c;4第二次…leetcode 123 买卖股票的最佳时机 III
题目链接
123. 买卖股票的最佳时机 III - 力扣LeetCode
做题过程
这里有两次交易机会。因此有5种状态。0没有操作1第一次买入2第一次卖出3第二次买入4第二次卖出。其他与股票问题相同。
解决方法
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 i 1; i prices.length; i) {dp[i][0] dp[i - 1][0];dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] - 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];}
}leetcode 188 买卖股票的最佳时机 IV
题目链接
188. 买卖股票的最佳时机 IV - 力扣LeetCode
做题过程
这道题需要多次交易。那就设置多次状态。一次买入一次卖出即可。
解决方法
class Solution {public int maxProfit(int k, int[] prices) {int[][] dp new int[prices.length][2 * k 1]; for (int j 1; j 2 * k 1; j 2) {dp[0][j] -prices[0];}for (int i 1; i prices.length; i) {for (int j 0; j 2 * k - 1; j 2) {dp[i][j 1] Math.max(dp[i - 1][j 1], dp[i - 1][j] - prices[i]);dp[i][j 2] Math.max(dp[i - 1][j 2], dp[i - 1][j 1] prices[i]);}}return dp[prices.length - 1][2 * k];}
}
