第29天--算法（Leetcode188,309）
188.买卖股票的最佳时机4
public int maxProfit(int k, int[] prices) { if (prices == null || prices.length == 0) { return 0; } int N = prices.length; if (k >= N / 2) { return allTrans(prices); } int dp[][] = new int[k + 1][N]; int ans = 0; for(int j = 1;j <= k;j ++) { int pre = dp[j][0]; int best = pre - prices[0]; for(int i = 1;i < N;i ++) { pre = dp[j - 1][i]; dp[j][i] = Math.max(dp[j][i - 1],prices[i] + best); best = Math.max(best,pre - prices[i]); ans = Math.max(ans,dp[j][i]); } } return ans; } public int allTrans(int[] prices) { int ans = 0; for (int i = 1; i < prices.length; i++) { ans += Math.max(prices[i] - prices[i - 1], 0); } return ans; } 309.买卖股票最佳时机含冷冻期 public static int maxProfit(int[] prices) { if (prices.length < 2) { return 0; } int N = prices.length; int[] buy = new int[N]; int[] sell = new int[N]; buy[1] = Math.max(-prices[0], -prices[1]); sell[1] = Math.max(0, prices[1] - prices[0]); for (int i = 2; i < N; i++) { buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]); sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]); } return sell[N - 1]; }