關(guān)鍵詞：“動態(tài)規(guī)劃”、“買賣股票”

題目描述

買賣股票的最佳時機(jī)含手續(xù)費(fèi)

這道題，有想到動態(tài)規(guī)劃來做，但是沒有想到合適的數(shù)組存儲意義?？戳藥讉€對應(yīng)題解，都是以對應(yīng)時間點(diǎn)的利潤作為含義。讀了好幾個，才明白其中含義。相比較之下，個人認(rèn)為，以當(dāng)前賬戶余額最為貼切。（利潤是一個兩個狀態(tài)的資產(chǎn)的差值的描述，且當(dāng)用戶擁有某個股票時，這股權(quán)也是用戶資產(chǎn)的一部分，而前者使用利潤來描述時是忽略了這樣的含義）

分析

根據(jù)題目內(nèi)容，我們可以知道：

1. 可以進(jìn)行多次交易
2. 手續(xù)費(fèi)的存在對頻繁的買賣行為形成約束。

解題思路（動態(tài)規(guī)劃）

存儲含義

用account[i] [0] 表示在第i天沒有擁有股票的賬戶余額最大值；

用account[i] [1] 表示在第i天擁有股票情況下的賬戶余額最大值；

轉(zhuǎn)移關(guān)系

第i+1天，沒有股票的最大賬戶余額account[i+1] [0]有兩種狀態(tài)轉(zhuǎn)移而來：

1. 在前一天就是不擁有股票的最大賬戶余額 account[i] [0]

2. 在前一天擁有股票的賬戶最大余額 account[i] [1]，并在第i+1天拋售

第i+1天，有股票的最大賬戶余額account[i+1] [1]有兩種狀態(tài)轉(zhuǎn)移而來：

1. 在前一天就是不擁有股票的最大賬戶余額 account[i] [0],并在第i+1天購買

2. 在前一天擁有股票的賬戶最大余額 account[i] [1]

初始狀態(tài)

假設(shè)初始賬戶余額為0，則在不擁有股票的情況下，最終賬戶余額就是所獲得的利潤。

第0天結(jié)束時

算法

INPUT: prices[], fee
OUTPUT: maxProfit

account[0][0] = 0 
account[0][1] = 0-prices[0] 

for i = 0 to prices.size()-1 :
    account[i+1][0] = max( account[i][0], account[i][1]+prices[i+1]-fee )
    account[i+1][1] = max( account[i][0]-prices[i+1], account[i][1] )

return account[prices.size()-1][0] 

數(shù)據(jù)結(jié)構(gòu)

數(shù)組

復(fù)雜度分析

時間復(fù)雜度和空間復(fù)雜度都是O(n)

代碼實(shí)現(xiàn)

/*
dp

INPUT: prices, fee
OUTPUT: maxProfit

suppose:
    dp[i][0] 不持有股票情況下的賬戶余額
    dp[i][0] 持有股票情況下的賬戶余額

transition：
    dp[i+1][0] = max( dp[i][0], dp[i][1]+prices[i+1]-fee )
    dp[i+1][1] = max( dp[i][0]-prices[i+1], dp[i][1] )
initialization:
    dp[0][0] = init_money
    dp[0][1] = init_money-prices[0]

*/

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

    }
};

相關(guān)問題

動態(tài)規(guī)劃

買賣股票系列

• LeetCode-121-買賣股票的最佳時機(jī) 劍指offer 63. 股票的最大利潤 買賣一次

• LeetCode-122-買賣股票的最佳時機(jī)2 無限制買賣次數(shù)

• LeetCode-123-買賣股票的最佳時機(jī)3 限制最多買賣2次

• LeetCode-188-買賣股票的最佳時機(jī)4 限制最多買賣k次

• LeetCode-309-買賣股票的最佳時機(jī)含冷凍期 限制冷凍期不可買賣

PS.

1. 相比較于其他已有的leetcode刷題筆記，我希望能夠提供相關(guān)的解題分析和部分相關(guān)問題的鏈接，使得大家能獲得一個較好的分析與相關(guān)問題的比較。

2. 偶爾會進(jìn)行類似題目的總結(jié)工作，有需要的讀者可以對這份工作進(jìn)行關(guān)注。

3. 如果你發(fā)現(xiàn)有相關(guān)的錯誤或者表述不當(dāng)不清晰的地方，請進(jìn)行評論，我會盡快進(jìn)行核對勘正。