本文主要是介绍代码随想录训练营第50天| 123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
123.买卖股票的最佳时机III
题目链接:123. 买卖股票的最佳时机 III - 力扣(LeetCode)
class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][5];if(prices.length == 1) {return 0;}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];}
}
状态机,dp数组可优化为2*5;
188.买卖股票的最佳时机IV
题目链接:188. 买卖股票的最佳时机 IV - 力扣(LeetCode)
class Solution {public int maxProfit(int k, int[] prices) {int[][] dp = new int[prices.length][2*k+1];if(prices.length == 1) {return 0;}for(int i = 0; i < 2*k+1; ++i) {dp[0][i] = i % 2 == 0 ? 0 : -prices[0];}for(int i = 1; i < prices.length; ++i) {for(int j = 1; j < 2*k+1; ++j) {dp[i][j] = j % 2 == 0 ? Math.max(dp[i-1][j], dp[i-1][j-1] + prices[i]) : Math.max(dp[i-1][j], dp[i-1][j-1]-prices[i]);}}return dp[prices.length-1][2*k];}
}
这篇关于代码随想录训练营第50天| 123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!