深圳网站建设推荐,提升网站性能,做网站代理商,阿里云上做网站套模板怎么做代码随想录算法训练营第五十九天| 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV
一、力扣123.买卖股票的最佳时机III
题目链接 思路#xff1a;之前的类型是用数组记录当前是持有还是不持有#xff0c;而这道题目多了两种状态#xff0c;即为#xff0c;第一次持…代码随想录算法训练营第五十九天| 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV
一、力扣123.买卖股票的最佳时机III
题目链接 思路之前的类型是用数组记录当前是持有还是不持有而这道题目多了两种状态即为第一次持有第一次不持有第二次持有第二次不持有。这个第几次是状态。 第一次持有 dp[i][0]目前是第一次持有的状态可以是之前持有的也可以是今天才持有的反正是第一次持有没有持有两次。 第一次不持有 dp[i][1]可以是昨天就不是持有状态也可以是今天才是非持有也就是进天才卖掉。 第二次持有 dp[i][2]可以昨天就是第二次持有也可以是今天才买入才变成第二次持有。 第二次不持有 dp[i][3]可以是昨天就不是第二次持有也可以今天才第二次卖掉。
class Solution {public int maxProfit(int[] prices) {int len prices.length;int[][] dp new int[len][4];dp[0][0] -prices[0];dp[0][1] 0;dp[0][2] -prices[0];dp[0][3] 0;for (int i 1; i len; i) {dp[i][0] Math.max(dp[i-1][0], -prices[i]);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] - prices[i]);dp[i][3] Math.max(dp[i-1][3], dp[i-1][2] prices[i]);}return Math.max(dp[len-1][1], dp[len-1][3]);}
}二、力扣188.买卖股票的最佳时机IV
题目链接 思路和上面的类似只不过是可以买入k次不是2次那么dp数组变成dp[nums.length][2*k1]即可
class Solution {public int maxProfit(int k, int[] prices) {int len prices.length, day 2 * k 1;int[][] dp new int[len][day];for (int i 1; i day; i) {if (i % 2 1) {dp[0][i] -prices[0];}}for (int i 1; i len; i) {for (int j 1; j day; j) {if (j % 2 1) {dp[i][j] Math.max(dp[i-1][j], dp[i-1][j-1] - prices[i]);}else {dp[i][j] Math.max(dp[i-1][j], dp[i-1][j-1] prices[i]);}}}return dp[len-1][day-1];}
}
