【前端算法】買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)—— 貪心算法、動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)

關(guān)注并將「趣談前端」設(shè)為星標(biāo)

每天定時(shí)分享技術(shù)干貨/優(yōu)秀開源/技術(shù)思維

題目描述

給定一個(gè)整數(shù)數(shù)組 prices，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 ；整數(shù) fee 代表了交易股票的手續(xù)費(fèi)用。

你可以無限次地完成交易，但是你每筆交易都需要付手續(xù)費(fèi)。如果你已經(jīng)購買了一個(gè)股票，在賣出它之前你就不能再繼續(xù)購買股票了。

返回獲得利潤的最大值。

注意：這里的一筆交易指買入持有并賣出股票的整個(gè)過程，每筆交易你只需要為支付一次手續(xù)費(fèi)。

示例 1：

輸入：prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出：8
解釋：能夠達(dá)到的最大利潤:  
在此處買入 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] 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路

思路1：動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)

動(dòng)態(tài)規(guī)劃三部曲

• 定義dp含義

• 定義dp[n][2]：
• n代表第n天有2種狀態(tài)，持有或者不持有
• dp[i][0] 第i天不持有獲得的最大利潤；
• dp[i][1] 第i天持有獲得的最大利潤；(tip:是持有不是買入)

• 定義狀態(tài)轉(zhuǎn)移方程：

  對于今天不持有，可以從兩個(gè)狀態(tài)轉(zhuǎn)移過來：1. 昨天也不持有；2. 昨天持有，今天賣出且支付手續(xù)費(fèi)fee。兩者取較大值。

  對于今天持有，可以從兩個(gè)狀態(tài)轉(zhuǎn)移過來：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],當(dāng)天不持有股票利潤一定大于當(dāng)天持有股票，因此返回dp[len-1][0]即可

時(shí)空復(fù)雜度

• 時(shí)間復(fù)雜度：O(n)，遍歷一遍即可。
• 空間復(fù)雜度：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]
};

優(yōu)化

降維：狀態(tài)轉(zhuǎn)移的時(shí)候，dp[i] 只會從 dp[i-1] 轉(zhuǎn)移得來，因此第一維可以去掉：

時(shí)空復(fù)雜度

• 時(shí)間復(fù)雜度：O(n)，遍歷一遍即可。
• 空間復(fù)雜度：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:貪心算法

• 將手續(xù)費(fèi)買入時(shí)進(jìn)行計(jì)算，即可得到一種貪心的方法；
• 我們定義buy表示：最大化利益的前提下，當(dāng)我們手上有一只股票時(shí)，那么他的買入最低價(jià)格。
• profit=prices[i]-buy;
• 但是此時(shí)我們賣出可能不是最優(yōu)解，比如：第二天價(jià)格繼續(xù)上升；
• 因此我們可以假設(shè)有個(gè)反悔操作，假設(shè)當(dāng)前手上有一只買入價(jià)格為prices[i]的股票，
• 將buy更新為prices[i]:buy=prices[i] ;
• 如果第二天價(jià)格繼續(xù)上升，我們將獲得prices[i+1]-prices[i],此時(shí)，加上前一天prices[i]-buy的收益，
• 由上可知，相當(dāng)于當(dāng)天不做任何操作，而在第二天賣出:prices[i+1]-buy
• 初始化為buy=prices[0]+fee;
• 如果當(dāng)前股票prices[i]+fee<buy;則我們更新最低買入價(jià)格buy;
• 如果當(dāng)前股票大于buy,則我們可以直接賣出獲得利潤
• 其余情況，不值得賣出；

時(shí)空復(fù)雜度

• 時(shí)間復(fù)雜度：O(n)，遍歷一遍即可。
• 空間復(fù)雜度：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
};

參考資料