动态规划专练:力扣第309、714题

力扣第309题-最佳买卖股票时机含冷冻期1.本题相比于力扣第122题-买卖股票的最佳时机Ⅱ区别仅在于卖出后距离下一次买入之间存在1天的冷冻期反映到递推公式上便是持有股票状态的最大金额需要取“昨天仍持有股票的最大金额dp[1][0]”和“前天甚至以前就已经卖掉股票后今天买入的最大金额dp[0][1] - prices[i]”中的较大值递推公式为dp[2][0] fmax(dp[1][0], dp[0][1] - prices[i])。未持有股票状态的最大金额递推公式保持不变。完整代码如下1. int maxProfit(int* prices, int pricesSize) { 2. // 数组长度为1无法完成交易利润为0 3. if (pricesSize 1) return 0; 4. 5. // dp[i][0]第i天持有股票的最大利润 6. // dp[i][1]第i天不持有股票的最大利润 7. // dp滚动数组dp0代表i-2天dp1代表i-1天dp2代表i天冷冻期股票问题 8. int dp[3][2]; 9. // 初始化第0天状态 10. dp[0][0] -prices[0]; 11. dp[0][1] 0; 12. // 初始化第1天状态 13. dp[1][0] fmax(dp[0][0], -prices[1]); 14. dp[1][1] fmax(dp[0][1], dp[0][0] prices[1]); 15. 16. // 从第2天开始遍历价格 17. for (int i 2; i pricesSize; i){ 18. // 当天持有前一天就持有 或 两天前不持有冷冻期已过今天买入 19. dp[2][0] fmax(dp[1][0], dp[0][1] - prices[i]); 20. // 当天不持有前一天就不持有 或 前一天持有今天卖出 21. dp[2][1] fmax(dp[1][1], dp[1][0] prices[i]); 22. 23. // 滚动更新状态向前移位 24. dp[0][0] dp[1][0]; 25. dp[0][1] dp[1][1]; 26. dp[1][0] dp[2][0]; 27. dp[1][1] dp[2][1]; 28. } 29. 30. // 最终最大利润一定是不持有股票的状态 31. return dp[1][1]; 32. }该算法时间复杂度为O(n)空间复杂度为O(1)。力扣第714题-买卖股票的最佳时机含手续费1.本题相比于力扣第122题-买卖股票的最佳时机Ⅱ区别仅在于每次卖出多了一个手续费fee那只需要在未持有股票状态的递推公式中将“今天卖出股票”这一项的现金多减去fee即可。未持有股票状态递推公式为dp[1][1] fmax(dp[0][1], dp[0][0] prices[i] - fee)。完整代码如下1. int maxProfit(int* prices, int pricesSize, int fee) { 2. // dp[0][0]前一天持有股票的最大利润 3. // dp[0][1]前一天不持有股票的最大利润 4. // dp[1][0]当天持有股票的最大利润 5. // dp[1][1]当天不持有股票的最大利润 6. int dp[2][2]; 7. // 初始化第0天状态 8. dp[0][0] -prices[0]; 9. dp[0][1] 0; 10. 11. for (int i 0; i pricesSize; i){ 12. // 当天持有之前就持有或前一天无股今天买入 13. dp[1][0] fmax(dp[0][0], dp[0][1] - prices[i]); 14. // 当天无股之前就无股或前一天持股今天卖出卖出扣除手续费fee 15. dp[1][1] fmax(dp[0][1], dp[0][0] prices[i] - fee); 16. 17. // 滚动更新前一天状态为当日状态供下一轮循环使用 18. dp[0][0] dp[1][0]; 19. dp[0][1] dp[1][1]; 20. } 21. 22. // 最大利润一定是不持有股票的状态 23. return dp[0][1]; 24. }该算法时间复杂度为O(n)空间复杂度为O(1)。2.本题也可以使用贪心算法。因为买了股票之后一定是卖出之后才会获益所以可以将实际买入价格buy等价于“价格 手续费”即prices[0] fee。1遍历数组如果当前价格prices[i]大于buy就卖出获得prices[i] – buy的利润。但此时卖出只是局部最优可能不是全局最优所以应提供一个反悔操作将buy更新为prices[i]这样一来如果第二天股票价格继续上升就会额外获得prices[i 1] - prices[i]的利润两天的利润相加后得到的便是真实利润。2如果当前价格加上手续费prices[i] fee仍小于buy那不如在今天购买此时支出最少。3.基于以上思想写出的完整代码如下1. int maxProfit(int* prices, int pricesSize, int fee) { 2. // buy记录买入成本买入价格手续费 3. int buy prices[0] fee; 4. // res累计总利润 5. int res 0; 6. 7. for (int i 1; i pricesSize; i){ 8. // 当前价格高于持仓成本卖出获利 9. if (prices[i] buy){ 10. res prices[i] - buy; 11. // 更新持仓价为当前价等价当天卖出又买回后续涨价可连续累加利润 12. buy prices[i]; 13. } 14. // 当前价格手续费比现有持仓成本更低更新更低买入点 15. else if (prices[i] fee buy){ 16. buy prices[i] fee; 17. } 18. } 19. 20. return res; 21. }该算法时间复杂度为O(n)空间复杂度为O(1)。