算法学习打卡day45｜动态规划：股票问题总结

Leetcode股票问题总结篇

• 动态规划的股票问题一共六道题，买卖股票最佳时机和买卖股票手续费都是一个类型的问题，维护好买入和卖出两个状态即可，方法一摸一样。而冷冻期也差不多就是状态多了点，买入、保持卖出、当日卖出、以及冷冻期四个状态。
• 做题方法还是动态规划五部曲：
  • 明确dp数组含义，这里六道题全部第i天都是手里买入状态或者卖出状态的现金数是多少，这篇文章下标0代表未持有，下标1代表持有。
  • 写出递推公式，下面写了最基本的，其他题的公式都是在这个基础上做了修改的：

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

    • 最佳时机2那道题就是在这个基础上，修改买入时的递推公式为dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]-prices[i - 1]);
    • 最佳时机3那道题是增加两个状态表示第二次买入和卖出：

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

    • 最佳时机4那道题是增加到2 * k个状态，那么内层就要变为双层循环为各个状态赋值了。

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

    • 冻结期那道题的递推公式就稍微复杂了，需要维护四个状态，分别是买入、保持卖出、当日卖出、以及冷冻期。

      	dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);dp[i][1] = 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];
      

    • 含手续费这道题和第二道题一摸一样，在卖出时减去手续费就行。
  • 初始化：每次买入的时候必须初始化为-price[0]，其他赋值为0即可。
  • 遍历顺序：由于需要用到 i - 1的资金，所以从前往后遍历

121. 买卖股票的最佳时机

力扣题目链接

代码实现：

int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size() + 1, vector(2, 0));dp[1][0] = 0, dp[1][1] = -prices[0];//二维数组0代表不持有，1代表持有for (int i = 2; i <= prices.size(); ++i) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);dp[i][1] = max(dp[i - 1][1], -prices[i - 1]);}return dp[prices.size()][0];}

• 动态规划二维数组滚动数组优化方式：

int maxProfit(vector<int>& prices) {vector<vector<int>> dp(2, vector(2, 0));//只记录当前天和前一天的状态即可dp[0][0] = 0, dp[0][1] = -prices[0];//二维数组0代表不持有，1代表持有for (int i = 1; i < prices.size(); ++i) {dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] + prices[i]);dp[i % 2][1] = max(dp[(i - 1) % 2][1], -prices[i]);//看实现通过求余，每次取的都是前一个元素值}return dp[(prices.size() + 1) % 2][0];//用+1，因为数组可能为空}

• 动态规划一维数组实现法，比二维实现更简洁

int maxProfit(vector<int>& prices) {vector<int> dp(2, 0);//只记录当前天的状态即可dp[0] = 0, dp[1] = -prices[0];//0代表不持有，1代表持有for (int i = 1; i < prices.size(); ++i) {dp[0] = max(dp[0], dp[1] + prices[i]);dp[1] = max(dp[1], -prices[i]);}return dp[0];}

• 贪心法实现（每次更新左边界为最小值，然后不断更新result结果）：

int maxProfit(vector<int>& prices) {int low = INT_MAX, result = 0;for (int i = 0; i < prices.size(); ++i) {low = min(low, prices[i]);result = max(result, prices[i] - low);}return result;}

买卖股票的最佳时机2

力扣题目链接
思路：

• 在上题基础上增加了买卖次数，修改买入时的计算方法即可。

代码实现

• 普通动态规划想法，直接计算每天的利润（和贪心类似）

int maxProfit(vector<int>& prices) {//dp[i] = max(dp[i - 1], dp[i - 1] + prices[i] - prices[i - 1]);vector<int> dp(prices.size(), 0);for (int i = 1; i < prices.size(); ++i) {dp[i] = max(dp[i - 1], dp[i - 1] + prices[i] - prices[i - 1]);}   return dp[prices.size() - 1];}

• 用双状态实现的方法（这里用一维数组实现的，也可以是二维）

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

• 贪心法

int maxProfit(vector<int>& prices) {int profit = 0;for (int i = 1; i < prices.size(); i++) {profit += max(prices[i] - prices[i - 1], 0);}return profit;}

• 双指针法

int maxProfit(vector<int>& prices) {int profit = 0, buy_index = 0;for (int i = 0; i < prices.size() - 1; i++) {if (prices[i] > prices[i + 1]) {profit += prices[i] - prices[buy_index];buy_index = i + 1;continue;}if (i + 1 == prices.size() - 1) {profit += prices[i + 1] - prices[buy_index];}}return profit;}

买卖股票的最佳时机3

力扣题目链接
思路：

• 这道题规定只能买卖两次，实现方法上面已经写过了，直接上代码

代码实现

int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(5, 0));dp[0][1] = -prices[0], dp[0][3] = -prices[0];//相当于当天买卖一次后再次买入for (int i = 1; i < prices.size(); ++i) {dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}return dp[prices.size() - 1][4];}

买卖股票的最佳时机4

力扣题目链接

思路：
买卖次数规定为k次，需要利用循环给每次买卖赋值。

代码实现

int maxProfit(int k, vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(k * 2 + 1, 0));for (int i = 1; i < 2 * k + 1; i += 2) {dp[0][i] = -prices[0];}for (int i = 1; i < prices.size(); ++i) {for (int j = 1; j <= 2 * k - 1; j += 2) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);}}return dp[prices.size() - 1][2 * k];}

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

力扣题目链接
题目描述：
在第二题基础上，增加了冷冻期，需要维护四个状态

代码实现

int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(4, 0));dp[0][0] = -prices[0];for (int i = 1; i < len; ++i) {dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);dp[i][1] = 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 max(dp[len - 1][1], max(dp[len - 1][2], dp[len - 1][3]));}

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

力扣题目链接
题目描述：
和第二题基本一样，卖出时减去手续费就行了

代码实现

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