阿里 代码随想录 188.买卖股票的最佳时机Ⅳ

思路本题要求至多有k次交易。动规五部曲1.确定dp数组以及下标的含义1dp[i][j]表示第i天的状态为j所剩下的最大现金为dp[i][j]。2j的状态表示为——0表示不操作——1表示第一次买入——2表示第一次卖出——3表示第二次买入——4表示第二次卖出3发现规律除了0以外偶数就是卖出奇数就是买入。4题目要求至多有k笔交易那么j的范围就定义为2*k1。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(); } }