股票類問題(動態規劃)

題目詳情

給定一個整數數組 prices，其中 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

思路:
股票類問題的一類(含手續費),我們同樣得可以畫出狀態機轉換圖:

dp[i][0]錶示第i天手裏沒股票的狀態
dp[i][1]錶示第i天手裏有股票的狀態
初始化好第0天的狀態即可遍曆每天的股票更新dp,詳細代碼如下:

我的代碼：

class Solution 
{
    
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
    
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = 0, dp[0][1] = -prices[0]; //初始化
        for (int i = 1; i < n; ++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]);
        }
        return dp[n - 1][0];
    }
};

可以看出,我們利用了vector存儲了各個狀態,但是狀態dp[i]只取决於dp[i-1],顯然O(n)空間複雜度太過繁雜,我們可以用兩個變量來存儲狀態,從而得到下面代碼:

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

本道題還可以利用貪心的策略:
貪心策略:保證以最低價買入股票(用一個變量存儲這個最低價格),最高價賣出股票
因為最高價無法保證,所以我們只要找到某一天的價格,賣出價格 > 買入價格 + 手續費 我們就立即賣出(賺一點是一點-並不是真正的賣出)
然後如果後面又找到 更高的價格 > 上次賣出的價格 >買入價格 + 手續費,
那麼我們在賺的錢的基礎上再加上這次賣出的差價 prices[i] - (minPrice + fee)
然後更新minPrice為當前價格减去手續費,以便查看後面還有沒有能賺的,或者找到低於這個minPrice的了,那麼就結束此段交易,再次進行一輪:以minPrice買入,然後不斷分析賺錢
詳細代碼:

class Solution 
{
    
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
    
        int res = 0;
        int minPrice = prices[0]; // 記錄最低價格
        for (int i = 1; i < prices.size(); i++) 
        {
    
            // 找到一個低價的,趕緊買入,結束上段交易開始新的(上段交易賺够了)
            if (prices[i] < minPrice) minPrice = prices[i];
            // 保持原有狀態（此時買入不便宜，賣則虧本） 注意這個if可以省略不寫
            if (prices[i] >= minPrice && prices[i] <= minPrice + fee) 
            {
    
                continue;
            }
            // 計算利潤，可能有多次計算利潤，最後一次計算利潤才是真正意義的賣出
            //如果今天的價格比上次記錄的 買入價格+手續費 還賺
            if (prices[i] > minPrice + fee) 
            {
    
                res += prices[i] - (minPrice + fee); // 就以i這天賣出 以上次minPrice買入的那個股票 會賺多少 ← 這就是上次少賺的利潤
                minPrice = prices[i] - fee; // 更新最小值,當前賣出價格减去手續費,從而以後的交易都會自動扣除手續費
            }
        }
        return res;
    }
};

涉及知識點:

1.動態規劃(dp)