java算法day50 | ● 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV

news/2024/5/20 16:59:12/文章来源:https://blog.csdn.net/weixin_44802990/article/details/137566605

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

在这里插入图片描述

思路： 这道题的关键就是如何设置dp数组的状态。用五种状态表示对股票持有或售出的不同阶段。代码随想录讲解视频

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][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];   }
}

时间复杂度：O(n)
空间复杂度：O(n × 5)

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

在这里插入图片描述

思路： 在上一题2次的基础上变为k次。可以发现规律：除了0以外，偶数就是卖出，奇数就是买入。
因此dp数组的维度为[n][k*2+1]

class Solution {public int maxProfit(int k, int[] prices) {int[][] dp=new int[prices.length][k*2+1];for(int i=0;i<k*2+1;i++){if(i%2==0){dp[0][i]=0;}else{dp[0][i]=-prices[0];}  }for(int i=1;i<prices.length;i++){for(int j=1;j<k*2+1;j++){if(j%2==0){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[prices.length-1][k*2];}
}