【前端算法】买卖股票的最佳时机含手续费—— 贪心算法、动态规划实现

题目描述

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：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
示例 2：

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

提示：

1 <= prices.length <= 5 * 104 1 <= prices[i] < 5 * 104 0 <= fee < 5 * 104

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/be…[1] 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

思路1：动态规划实现

动态规划三部曲

• 定义dp含义
  • 定义dp[n][2]：
  • n代表第n天有2种状态，持有或者不持有
  • dp[i][0] 第i天不持有获得的最大利润；
  • dp[i][1] 第i天持有获得的最大利润；(tip:是持有不是买入)
• 定义状态转移方程： 对于今天不持有，可以从两个状态转移过来：1. 昨天也不持有；2. 昨天持有，今天卖出且支付手续费fee。两者取较大值。 对于今天持有，可以从两个状态转移过来：1. 昨天也持有；2. 昨天不持有，今天买入。两者取较大值。
  • dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);
  • dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
• 初始化dp;
  • 不持有:dp[0][0]=0;
  • 持有:dp[0][1]=-prices[0] ((即花了price[0] 的钱买入))

由于dp[n][0]>dp[i][1],当天不持有股票利润一定大于当天持有股票，因此返回dp[len-1][0]即可

时空复杂度

• 时间复杂度：O(n)，遍历一遍即可。
• 空间复杂度：O(n)

代码

function maxProfit(prices: number[], fee: number): number {
    
    let len=prices.length;
     // define dp
     let dp=new Array(len);
     for(let i=0;i<len;i++){
         dp[i]=new Array(2).fill(0);
     }
     // init dp 
     dp[0][0]=0;
     dp[0][1]=-prices[0];
     for(let i=1;i<len;i++){
         dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
         dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);
     }
     console.log(dp);
    return dp[len-1][0]
};

优化

降维：状态转移的时候，dp[i] 只会从 dp[i-1] 转移得来，因此第一维可以去掉：

时空复杂度

• 时间复杂度：O(n)，遍历一遍即可。
• 空间复杂度：O(1)

 function maxProfit(prices: number[], fee: number): number {
    
    let len:number=prices.length;
     // define dp
     let dp=new Array(2);

     // init dp 
     dp[0]=0;
     dp[1]=-prices[0];
     for(let i=1;i<len;i++){
         let temp=dp[0]
         dp[0]=Math.max(dp[0],dp[1]+prices[i]-fee);
         dp[1]=Math.max(temp-prices[i],dp[1]);
     }
     console.log(dp);
    return dp[0]
};

思路2:贪心算法

• 将手续费买入时进行计算，即可得到一种贪心的方法；
• 我们定义buy表示：最大化利益的前提下，当我们手上有一只股票时，那么他的买入最低价格。
  • profit=prices[i]-buy;
  • 但是此时我们卖出可能不是最优解，比如：第二天价格继续上升；
  • 因此我们可以假设有个反悔操作，假设当前手上有一只买入价格为prices[i]的股票，
  • 将buy更新为prices[i]:buy=prices[i] ;
  • 如果第二天价格继续上升，我们将获得prices[i+1]-prices[i],此时，加上前一天prices[i]-buy的收益，
  • 由上可知，相当于当天不做任何操作，而在第二天卖出:prices[i+1]-buy
  • 初始化为buy=prices[0]+fee;
  • 如果当前股票prices[i]+fee<buy;则我们更新最低买入价格buy;
  • 如果当前股票大于buy,则我们可以直接卖出获得利润
  • 其余情况，不值得卖出；

时空复杂度

• 时间复杂度：O(n)，遍历一遍即可。
• 空间复杂度：O(1)

function maxProfit(prices: number[], fee: number): number {
  let len=prices.length;
  let buy=prices[0]+fee;
  let profit=0;
  for(let i=1;i<len;i++){
      if(prices[i]+fee<buy){
          buy=prices[i]+fee;
      }else if(prices[i]>buy){
          profit+=prices[i]-buy
          buy=prices[i]
      }
  }// end of for 
  return profit
};

参考资料

[1]https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee: https://link.juejin.cn/?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fbest-time-to-buy-and-sell-stock-with-transaction-fee