随想录算法训练营第五十一天|309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

309.最佳买卖股票时机含冷冻期

public class Solution {public int MaxProfit(int[] prices) {if(prices.Length<2){return 0;}int [,]dp=new int[prices.Length,4];dp[0,0]=-prices[0];for(int i=1;i<prices.Length;i++){dp[i,0]=Math.Max(dp[i-1,0],Math.Max(dp[i-1,3]-prices[i],dp[i-1,1]-prices[i]));dp[i,1]=Math.Max(dp[i-1,1],dp[i-1,3]);dp[i,2]=dp[i-1,0]+prices[i];dp[i,3]=dp[i-1,2];}return Math.Max(dp[prices.Length-1,3],Math.Max(dp[prices.Length-1,1],dp[prices.Length-1,2]));}
}

分为四种状态，达到买入股票状态（状态一），达到保持卖出股票状态（状态二），达到今天就卖出股票状态（状态三），达到冷冻期状态（状态四）。然后列出状态转移方程。

714.买卖股票的最佳时机含手续费

public class Solution {public int MaxProfit(int[] prices, int fee) {if(prices.Length==0){return 0;}int[,]dp=new int[prices.Length,2];dp[0,0]=-prices[0];for(int i=1;i<prices.Length;i++){dp[i,0]=Math.Max(dp[i-1,0],dp[i-1,1]-prices[i]);dp[i,1]=Math.Max(dp[i-1,1],dp[i-1,0]+prices[i]-fee);}return Math.Max(dp[prices.Length-1,1],dp[prices.Length-1,0]);}
}

在买股票II的基础上在卖出当天减去手续费即可实现。