算法练习第五十天|123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV

123. 买卖股票的最佳时机 III
188. 买卖股票的最佳时机 IV

123.买卖股票的最佳时机III

class Solution {public int maxProfit(int[] prices) {//dp[i][j] 第i天买卖股票获得的最大利润/**j=0不操作j=1第一次持有j=2第一次不持有j=3第二次持有j=4第二次不持有dp[i][0] = dp[i-1][0]dp[i][1] = max(dp[i-1][1],dp[i-1][0] - price[i])dp[i][2] = max(dp[i-1][2],dp[i-1][1] + price[i])dp[i][3] = max(dp[i-1][3],dp[i-1][2] - price[i])dp[i][4] = max(dp[i-1][4],dp[i-1][3] + price[i])*/if (prices.length == 0) return 0;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 Math.max(dp[prices.length-1][2],dp[prices.length-1][4]);}
}

188.买卖股票的最佳时机IV

class Solution {public int maxProfit(int k, int[] prices) {//dp[i][j] 第i天买卖股票获得的最大利润/**j=0不操作j=1第一次持有j=2第一次不持有j=3第二次持有j=4第二次不持有............j=2k 第k次不持有dp[i][0] = dp[i-1][0]dp[i][1] = max(dp[i-1][1],dp[i-1][0] - price[i])dp[i][2] = max(dp[i-1][2],dp[i-1][1] + price[i])dp[i][3] = max(dp[i-1][3],dp[i-1][2] - price[i])dp[i][4] = max(dp[i-1][4],dp[i-1][3] + price[i]).。。。。。。dp[i][2k] = max(dp[i-1][2k],dp[i-1][2k-1] + price[i])*/if (prices.length == 0) return 0;int[][] dp = new int[prices.length][2*k+1];// dp数组的初始化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= 0;j<2*k;j+=2){//dp[i][j] = dp[i-1][j];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];}
}