188 买卖股票的最佳时机IV（状态机DP）（灵神笔记）

本文主要是介绍188 买卖股票的最佳时机IV（状态机DP）（灵神笔记），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

买卖股票的最佳时机IV
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000

题解

记忆化搜索（超时）

class Solution {private int[] prices;private int[][][] cache;public int maxProfit(int k, int[] prices) {this.prices = prices;int n = prices.length;cache = new int[n][k + 1][2];for (int i = 0; i < n; i++) {for (int j = 0; j <= k; j++) {Arrays.fill(cache[i][j],-1);}}return dfs(n - 1, k, 0);}private int dfs(int i, int j, int hold) {if (j < 0) {return Integer.MIN_VALUE / 2;}if (i < 0) {return hold == 1 ? Integer.MIN_VALUE / 2 : 0;}if (cache[i][j][hold] != -1) {return cache[i][j][hold];}if (hold == 1) {//最后未持有股票，手上的股票一定会被卖掉，j-1可以是买股票的时候，也可以是卖股票的时候return Math.max(dfs(i - 1, j, 1), dfs(i - 1, j - 1, 0) - prices[i]);}return Math.max(dfs(i - 1, j, 0), dfs(i - 1, j, 1) + prices[i]);}
}

递推

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

空间优化

class Solution {public int maxProfit(int k, int[] prices) {int[][] f = new int[k + 2][2];for (int j = 1; j <= k + 1; j++) {f[j][1] = Integer.MIN_VALUE / 2;}f[0][0] = Integer.MIN_VALUE / 2;for (int p : prices) {for (int j = k + 1; j > 0; j--) {f[j][0] = Math.max(f[j][0], f[j][1] + p);f[j][1] = Math.max(f[j][1], f[j - 1][0] - p);}}return f[k + 1][0];}
}

恰好完成k笔交易

递归到i<0时，只有j=0是合法的
f[0][1][0] = 0

	private int dfs(int i, int j, int hold) { //记忆化搜索if (j < 0) {return Integer.MIN_VALUE / 2;}if (i < 0) {return hold == 1 && j > 0 ? Integer.MIN_VALUE / 2 : 0;}if (cache[i][j][hold] != -1) {return cache[i][j][hold];}if (hold == 1) {return Math.max(dfs(i - 1, j, 1), dfs(i - 1, j - 1, 0) - prices[i]);}return Math.max(dfs(i - 1, j, 0), dfs(i - 1, j, 1) + prices[i]);}public int maxProfit(int k, int[] prices) { //递推int n = prices.length;int[][][] f = new int[n + 1][k + 2][2];for (int i = 0; i < n; i++) {for (int j = 0; j <= k + 1; j++) {Arrays.fill(f[i][j],Integer.MIN_VALUE / 2);}}f[0][1][0] = 0for (int i = 0; i < n; i++) {for (int j = 1; j <= k + 1; j++) {f[i + 1][j][0] = Math.max(f[i][j][0], f[i][j][1] + prices[i]);f[i + 1][j][1] = Math.max(f[i][j][1], f[i][j - 1][0] - prices[i]);}}return f[n][k + 1][0];}

至少完成k笔交易

与122相同，至少0次等价于可以无限次交易，f[0][0][0] = 0，其余等于负无穷， 最前面无需插入状态，则循环k次即可
f[i + 1][0][0] = Math.max(f[i][0][0], f[i][0][1] + prices[i]);
f[i + 1][0][1] = Math.max(f[i][0][1], f[i][0][0] - prices[i]);

	private int dfs(int i, int j, int hold) { //记忆化搜索if (i < 0) {return hold == 1 && j > 0 ? Integer.MIN_VALUE / 2 : 0;}if (cache[i][j][hold] != -1) {return cache[i][j][hold];}if (hold == 1) {return Math.max(dfs(i - 1, j, 1), dfs(i - 1, j - 1, 0) - prices[i]);}return Math.max(dfs(i - 1, j, 0), dfs(i - 1, j, 1) + prices[i]);}public int maxProfit(int k, int[] prices) { //递推int n = prices.length;int[][][] f = new int[n + 1][k + 2][2];for (int i = 0; i < n; i++) {for (int j = 0; j <= k + 1; j++) {Arrays.fill(f[i][j],Integer.MIN_VALUE / 2);}}f[0][0][0] = 0for (int i = 0; i < n; i++) {f[i + 1][0][0] = Math.max(f[i][0][0], f[i][0][1] + prices[i]);f[i + 1][0][1] = Math.max(f[i][0][1], f[i][0][0] - prices[i]);for (int j = 1; j <= k; j++) {f[i + 1][j][0] = Math.max(f[i][j][0], f[i][j][1] + prices[i]);f[i + 1][j][1] = Math.max(f[i][j][1], f[i][j - 1][0] - prices[i]);}}return f[n][k + 1][0];