day114（3.16）——leetcode面试经典150

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

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

题目：

题解：

class Solution { public int maxProfit(int k, int[] prices) { if(prices==null || prices.length < 2) { return 0; } int n = prices.length; //只依赖前一天 int[][] dp = new int[k+1][2]; for(int i=0;i<=k;i++) { dp[i][0]=0; dp[i][1]=-prices[0]; } for(int i=1;i<n;i++) { for(int j=1;j<=k;j++) { // 卖出：保持不持有 OR (持有 + 今天卖出) dp[j][0]=Math.max(dp[j][0], prices[i]+dp[j][1]); // 买入：保持持有 OR (完成 j-1 笔后不持有 - 今天买入) dp[j][1]=Math.max(dp[j][1], dp[j-1][0]-prices[i]); } } return dp[k][0]; } }