动态规划-状态机（188.买卖股票的最佳时机IV）

状态分类：

f[i,j,0]考虑前i只股票，进行了j笔交易，目前未持有股票 所能获得最大利润

f[i,j,1]考虑前i只股票，进行了j笔交易，目前持有股票 所能获得最大利润

状态转移：

f[i][j][0] = Math.max(f[i-1][j][0],f[i-1][j][1]+prices[i]);

f[i][j][1] = Math.max(f[i-1][j][1],f[i-1][j-1][0]-prices[i]);

 

class Solution { static int INF = 0x3f3f3f3f; public int maxProfit(int k, int[] prices) { int n = prices.length; int f[][][] = new int[n+1][k+1][2]; for(int i = 0;i <= n;i++){ for(int j = 0;j <= k;j++){ Arrays.fill(f[i][j],-INF); } } for(int i = 0;i <= n;i++)f[i][0][0] = 0; for(int i = 1;i <= n;i++){ for(int j = 1;j <= k;j++){ f[i][j][0] = Math.max(f[i-1][j][0],f[i-1][j][1]+prices[i-1]); f[i][j][1] = Math.max(f[i-1][j][1],f[i-1][j-1][0]-prices[i-1]); } } int ans = 0; for(int i = 0;i <= k;i++){ ans = Math.max(ans,f[n][i][0]); } return ans; } }

还有一位大佬的看不懂的极妙解法--滚动的dp？

// java class Solution { public int maxProfit(int k, int[] prices) { int[] buy = new int[k], sell = new int[k]; Arrays.fill(buy, -prices[0]); for (int i = 1; i < prices.length; i++) { for (int j = 0, pre = 0; j < k; j++) { buy[j] = (pre = Math.max(buy[j], pre - prices[i])); sell[j] = (pre = Math.max(sell[j], pre + prices[i])); } } return Math.max(sell[k - 1], 0); } }