【Day55】代码随想录之动态规划_买卖股票含冷冻期和手续费

本文主要是介绍【Day55】代码随想录之动态规划_买卖股票含冷冻期和手续费，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- - 动态规划理论基础
  - - 动规五部曲：
    - 出现结果不正确：
  - 1. 最佳买卖股票的时机含冷冻期
  - 2. 买卖股票的最佳时机含手续费

动态规划理论基础

动规五部曲：

确定dp数组下标及dp[i] 的含义。
递推公式：比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。
初始化dp数组。
确定遍历顺序：从前到后or其他。
打印。

出现结果不正确：

打印dp日志和自己想的一样：递推公式、初始化或者遍历顺序出错。
打印dp日志和自己想的不一样：代码实现细节出现问题。

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

参考文档：代码随想录

分析：
加入冷冻期的概念，如果当前卖出了会有一天的冷冻期，这一天不能买入股票，所以节点的状态增加为持有当场卖出冷冻期和卖出状态四种。卖出状态是说明可以持有股票了。
递推公式：

dp[i][0] = max(dp[i-1][0], max(dp[i-1][2]-prices[i], dp[i-1][3]-prices[i]));
dp[i][1] = dp[i-1][0] + prices[i];
dp[i][2] = dp[i-1][1];
dp[i][3] = max(dp[i-1][3], dp[i-1][2]);

代码：

class Solution {
public:int maxProfit(vector<int>& prices) {//比较重要的是状态的细分vector<vector<int>> dp(prices.size(), vector<int>(4, 0));dp[0][0] = -prices[0];//持有dp[0][1] = 0;//当天卖出dp[0][2] = 0;//冷冻期dp[0][3] = 0;//卖出状态for(int i = 1; i < prices.size(); i++){dp[i][0] = max(dp[i-1][0], max(dp[i-1][2]-prices[i], dp[i-1][3]-prices[i]));dp[i][1] = dp[i-1][0] + prices[i];dp[i][2] = dp[i-1][1];dp[i][3] = max(dp[i-1][3], dp[i-1][2]);}return max(max(dp[prices.size()-1][0],dp[prices.size()-1][1]),max(dp[prices.size()-1][2], dp[prices.size()-1][3]));}
};

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

参考文档：代码随想录

分析：
手续费什么是否付呢？需要卖出的时候就要付了。每个节点的状态有两个，持有和不持有手里的钱。
递推公式：

dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);

代码：

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {vector<vector<int>> dp(prices.size(), vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < prices.size(); i++){dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]);dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);}return max(0,max(dp[prices.size()-1][1], dp[prices.size()-1][0]));}
};