代码随想录算法训练营 动态规划part11

一、买卖股票的最佳时机III  

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

请选一个喜欢的吧/(ㄒoㄒ)/~~123. 买卖股票的最佳时机 III - 力扣（LeetCode）

class Solution {public int maxProfit(int[] prices) {if(prices==null || prices.length==0) {return 0;}int n = prices.length;//定义二维数组，5种状态  int[][] dp = new int[n][5];//初始化第一天的状态dp[0][0] = 0;dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];dp[0][4] = 0;for(int i=1;i<n;++i) {//dp[i][0]相当于初始状态，它只能从初始状态转换来dp[i][0] = dp[i-1][0];//处理第一次买入、第一次卖出dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);//处理第二次买入、第二次卖出dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);}//返回最大值return Math.max(Math.max( Math.max(dp[n-1][0],dp[n-1][1]),Math.max(dp[n-1][2],dp[n-1][3]) ),dp[n-1][4]);}
}

class Solution {public int maxProfit(int k, int[] prices) {if(prices==null || prices.length==0) {return 0;}return dfs(0,0,0,k,prices);}//计算k次交易，index表示当前是哪天，status是买卖状态，coutnt为交易次数private int dfs(int index, int status, int count, int k, int[] prices) {if(index==prices.length || count==k) {return 0;}int a=0,b=0,c=0;//保持不动a = dfs(index+1,status,count,k,prices);if(status==1) {//卖一股，并将交易次数+1b = dfs(index+1,0,count+1,k,prices)+prices[index];} else {//买一股c = dfs(index+1,1,count,k,prices)-prices[index];}return Math.max(Math.max(a,b),c);}
}