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

一、递归

设定在买入的时候支付手续费
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][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);（前一天每持有，或者前一天没持有，在今天买入）

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices, int fee) {
  4.         vector<vector<int>> dp(prices.size(),vector<int>(2));
  5.         dp[0][0] = -prices[0]-fee;
  6.         dp[0][1] = 0;
  7.         for(int i=1;i<prices.size();i++)
  8.         {
  9.              dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i]-fee);
  10.              dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);
  11.         }
  12.         return dp[prices.size()-1][1];
  13.     }
  14. };