阿里 代码随想录 188.买卖股票的最佳时机Ⅳ
思路：本题要求至多有k次交易。
动规五部曲：
1.确定dp数组以及下标的含义：
（1）dp[i][j]表示第i天的状态为j，所剩下的最大现金为dp[i][j]。
（2）j的状态表示为：
——0表示不操作；
——1表示第一次买入；
——2表示第一次卖出；
——3表示第二次买入；
——4表示第二次卖出；
（3）发现规律：除了0以外，偶数就是卖出，奇数就是买入。
（4）题目要求至多有k笔交易，那么j的范围就定义为2*k+1。
2.确定递推公式：
（1）注意：dp[i][1]表示的是第i天买入股票的状态，并不是说一定要第i天买入股票。
（2）达到dp[i][1]状态，有两个具体操作：
——第i天买入股票了，那么dp[i][1] = dp[i - 1][0] - prices[i]
——第i天没有操作，而是沿用前一天买入的状态，即dp[i][1] = dp[i - 1][1]
——选最大的，所以dp[i][1] = max(dp[i - 1][0] - prices[i],dp[i - 1][1])
（3）同理dp[i][2]也有两个具体操作：
——第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
——第i天没有操作，而是沿用前一天卖出的状态，即dp[i][2] = dp[i - 1][2]
——选最大的，所以dp[i][2] = max(dp[i - 1][1] + prices[i],dp[i - 1][2])
（4）同理可类比剩下的状态，代码如下：
for (int j = 0; j < 2 * k - 1; j += 2) { dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]); dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); }3.dp数组如何初始化：
（1）如果第0天没有操作，那就是0。即dp[0][0] = 0。
（2）如果第0天做第一次买入的操作，则dp[0][1] = -prices[0]。
（3）如果第0天做第一次卖出的操作，则就是当天买入当天卖出，dp[0][2] = 0。
（4）如果第0天做第二次买入的操作，就是当天买入当天卖出后，再买入一次，dp[0][3] = -prices[0]。
（5）同理第二次卖出初始化为dp[0][4] = 0。
（6）同理可推出dp[0][j]：当j为奇数的时候都初始化为-prices[0]，代码如下所示：
for (int j = 1; j < 2 * k; j += 2) { dp[0][j] = -prices[0]; }4.确定遍历顺序：一定是从前向后遍历，因为dp[i]依靠dp[i - 1]的数值。
5.举例推导dp数组：以输入[1,2,3,4,5]，k = 2为例。最后一次卖出，一定是利润最大的，dp[prices.size() - 1][2*k]，即红色部分，就是最后求解。
附代码：
（一）二维dp数组
class Solution { public int maxProfit(int k, int[] prices) { int len = prices.length; if(len == 0){ return 0; } // [天数][股票状态] // 股票状态：奇数表示第k次交易持有/买入；偶数表示第k次交易不持有/卖出，0表示没有操作 int[][] dp = new int[len][k * 2 + 1]; // dp数组的初始化 for(int j = 1;j < k * 2;j += 2){ dp[0][j] = -prices[0]; } for(int i = 1;i < len;i++){ // j的范围是1到2k的闭区间 // 且j为奇数时表示买入，j为偶数时表示卖出 // 因此j从0开始，j + 1表示奇数，j + 2表示偶数，且两个两个遍历：j += 2 for(int j = 0;j < k * 2 - 1;j += 2){ dp[i][j + 1] = Math.max(dp[i - 1][j + 1],dp[i - 1][j] - prices[i]); dp[i][j + 2] = Math.max(dp[i - 1][j + 2],dp[i - 1][j + 1] + prices[i]); } } return dp[len - 1][k * 2]; } }（二）一维dp数组
class Solution { public int maxProfit(int k, int[] prices) { if(prices.length == 0){ return 0; } if(k == 0){ return 0; } //记录k次交易的状态即可 //每次交易都有买入、卖出两个状态，所以要乘2 int[] dp = new int[2 * k]; //dp[0]代表第一次交易的买入 //dp[1]代表第一次交易的卖出 //dp[2]代表第二次交易的买入 //dp[3]代表第二次交易的卖出 for(int i = 0;i < dp.length/2;i++){ dp[i * 2] = -prices[0]; } for(int i = 1;i <= prices.length;i++){ //初始化dp[0]和dp[1] dp[0] = Math.max(dp[0], -prices[i - 1]); dp[1] = Math.max(dp[1],dp[0] + prices[i - 1]); for(int j = 2;j < dp.length;j += 2){ //要么保持不变，要么没有就买，有了就卖 dp[j] = Math.max(dp[j],dp[j - 1] - prices[i - 1]); dp[j + 1] = Math.max(dp[j + 1],dp[j] + prices[i - 1]); } } //dp[dp.length - 1]代表完成第k次交易后不持有的最大利润，正是所求值 //求的是利润，不是价格，不能用prices return dp[dp.length - 1]; } }ACM模式：
import java.util.Scanner; class Solution { public int maxProfit(int k, int[] prices) { int len = prices.length; if (len == 0) { return 0; } // [天数][股票状态] // 股票状态：奇数表示第k次交易持有/买入；偶数表示第k次交易不持有/卖出，0表示没有操作 int[][] dp = new int[len][k * 2 + 1]; // dp数组的初始化 for (int j = 1; j < k * 2; j += 2) { dp[0][j] = -prices[0]; } for (int i = 1; i < len; i++) { // j的范围是1到2k的闭区间 // 且j为奇数时表示买入，j为偶数时表示卖出 // 因此j从0开始，j + 1表示奇数，j + 2表示偶数，且两个两个遍历：j += 2 for (int j = 0; j < k * 2 - 1; j += 2) { dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]); dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); } } return dp[len - 1][k * 2]; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取最大交易次数k int k = scanner.nextInt(); // 读取数组长度 int n = scanner.nextInt(); // 读取价格数组 int[] prices = new int[n]; for (int i = 0; i < n; i++) { prices[i] = scanner.nextInt(); } // 计算最大利润（最多k次交易） Solution solution = new Solution(); int result = solution.maxProfit(k, prices); System.out.println(result); scanner.close(); } }