leetcode 链接：714. 买卖股票的最佳时机含手续费

题目

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

解答 & 代码

动态规划：

设置动态规划数组 dp
- dp[i][0] 代表第 i 天交易完手里没有股票的最大利润
- dp[i][1] 代表第 i 天交易完手里有股票的最大利润
状态转移方程：
- dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
  - 分析：dp[i][0] 表示这天交易完手里没有股票，那么可能第 i - 1 天交易完手里就没有股票，即 dp[i - 1][0]；也可能第 i - 1 天交易完手里有股票，但第 i 天卖掉了，即 dp[i - 1][1] + prices[i] - fee
- dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])
  - 分析：dp[i][1] 表示这天交易完手里有股票，那么可能第 i - 1 天交易完手里没有股票，而第 i 天买了股票，即 dp[i - 1][0] - prices[i]；也有可能第 i - 1 天交易完手里就有股票了，即 dp[i - 1][1]

初始化：dp[0][0] = 0, dp[0][1] = -prices[0]

class Solution {
public:
  int maxProfit(vector<int>& prices, int fee) {
      int size = prices.size();
      if(size <= 1)
          return 0;

      // 动态规划数组，dp[i][0] 代表第 i 天交易完手里没有股票的最大利润
      // dp[i][1] 代表第 i 天交易完手里有股票的最大利润
      vector<vector<int>> dp(size, vector<int>(2, 0));
      // 初始化
      dp[0][0] = 0;
      dp[0][1] = -prices[0];
      // 状态转移
      for(int i = 1; i < size; ++i)
      {
          dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
          dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
      }
      return max(dp[size - 1][0], dp[size - 1][1]); 
  }
};

执行结果： ``` 执行结果：通过

执行用时：192 ms, 在所有 C++ 提交中击败了 28.43% 的用户内存消耗：88.7 MB, 在所有 C++ 提交中击败了 10.81% 的用户 ```

CodeTop 企业题库

[中等] 714. 买卖股票的最佳时机含手续费

题目

解答 & 代码