淺談什麼是動態規劃以及相關的「股票」算法題：一網打盡「買賣股票的最佳時機」

本文首發於公眾號「五分鐘學算法」，是系列文章之一。

個人網站：

動態規劃

1 概念

  動態規劃算法是通過拆分問題，定義問題狀態和狀態之間的關係，使得問題能夠以遞推（或者說分治）的方式去解決。在學習動態規劃之前需要明確掌握幾個重要概念。

  階段：對於一個完整的問題過程，適當的切分為若干個相互聯繫的子問題，每次在求解一個子問題，則對應一個階段，整個問題的求解轉化為按照階段次序去求解。

  狀態：狀態表示每個階段開始時所處的客觀條件，即在求解子問題時的已知條件。狀態描述了研究的問題過程中的狀況。

  決策：決策表示當求解過程處於某一階段的某一狀態時，可以根據當前條件作出不同的選擇，從而確定下一個階段的狀態，這種選擇稱為決策。

  策略：由所有階段的決策組成的決策序列稱為全過程策略，簡稱策略。

  最優策略：在所有的策略中，找到代價最小，性能最優的策略，此策略稱為最優策略。

  狀態轉移方程：狀態轉移方程是確定兩個相鄰階段狀態的演變過程，描述了狀態之間是如何演變的。

2 使用場景

能採用動態規劃求解的問題的一般要具有 3 個性質：

  （1）最優化：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。子問題的局部最優將導致整個問題的全局最優。換句話說，就是問題的一個最優解中一定包含子問題的一個最優解。

  （2）無後效性：即某階段狀態一旦確定，就不受這個狀態以後決策的影響。也就是說，某狀態以後的過程不會影響以前的狀態，只與當前狀態有關，與其他階段的狀態無關，特別是與未發生的階段的狀態無關。

   （3）重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質並不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢）

3 算法流程

  （1）劃分階段：按照問題的時間或者空間特徵將問題劃分為若干個階段。
  （2）確定狀態以及狀態變量：將問題的不同階段時期的不同狀態描述出來。
  （3）確定決策並寫出狀態轉移方程：根據相鄰兩個階段的各個狀態之間的關係確定決策。
  （4）尋找邊界條件：一般而言，狀態轉移方程是遞推式，必須有一個遞推的邊界條件。
  （5）設計程序，解決問題

實戰練習

下面的三道算法題都是來源於 LeetCode 上與股票買賣相關的問題 ，我們按照 動態規劃 的算法流程來處理該類問題。

股票買賣這一類的問題，都是給一個輸入數組，裏面的每個元素表示的是每天的股價，並且你只能持有一支股票（也就是你必須在再次購買前出售掉之前的股票），一般來說有下面幾種問法：

• 只能買賣一次
• 可以買賣無數次
• 可以買賣 k 次

需要你設計一個算法去獲取最大的利潤。

買賣股票的最佳時機

題目來源於 LeetCode 上第 121 號問題：買賣股票的最佳時機。題目難度為 Easy，目前通過率為 49.4% 。

題目描述

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。

如果你最多只允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能獲取的最大利潤。

注意你不能在買入股票前賣出股票。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
     注意利潤不能是 7-1 = 6, 因為賣出價格需要大於買入價格。

示例 2:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

題目解析

我們按照動態規劃的思想來思考這道問題。

狀態

有 買入（buy） 和 賣出（sell） 這兩種狀態。

轉移方程

對於買來說，買之後可以賣出（進入賣狀態），也可以不再進行股票交易（保持買狀態）。

對於賣來說，賣出股票后不在進行股票交易（還在賣狀態）。

只有在手上的錢才算錢，手上的錢購買當天的股票后相當於虧損。也就是說當天買的話意味着損失-prices[i]，當天賣的話意味着增加prices[i]，當天賣出總的收益就是 buy+prices[i] 。

所以我們只要考慮當天買和之前買哪個收益更高，當天賣和之前賣哪個收益更高。

• buy = max(buy, -price[i]) （注意：根據定義 buy 是負數）
• sell = max(sell, prices[i] + buy)

邊界

第一天 buy = -prices[0], sell = 0，最後返回 sell 即可。

代碼實現

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int buy = -prices[0], sell = 0;
        for(int i = 1; i < prices.length; i++) {
            buy = Math.max(buy, -prices[i]);
            sell = Math.max(sell, prices[i] + buy);

        }
        return sell;
    }
}

買賣股票的最佳時機 II

題目來源於 LeetCode 上第 122 號問題：買賣股票的最佳時機 II。題目難度為 Easy，目前通過率為 53.0% 。

題目描述

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參与多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
     隨後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

示例 2:

輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接連購買股票，之後再將它們賣出。
     因為這樣屬於同時參与了多筆交易，你必須在再次購買前出售掉之前的股票。

示例 3:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

題目解析

狀態

有 買入（buy） 和 賣出（sell） 這兩種狀態。

轉移方程

對比上題，這裏可以有無限次的買入和賣出，也就是說 買入 狀態之前可擁有 賣出 狀態，所以買入的轉移方程需要變化。

• buy = max(buy, sell – price[i])
• sell = max(sell, buy + prices[i] )

邊界

第一天 buy = -prices[0], sell = 0，最後返回 sell 即可。

代碼實現

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int buy = -prices[0], sell = 0;
        for(int i = 1; i < prices.length; i++) {
            sell = Math.max(sell, prices[i] + buy);
            buy = Math.max( buy,sell - prices[i]);
        }
        return sell;
    }
}

買賣股票的最佳時機 III

題目來源於 LeetCode 上第 123 號問題：買賣股票的最佳時機 III。題目難度為 Hard，目前通過率為 36.1% 。

題目描述

給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。

注意: 你不能同時參与多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:

輸入: [3,3,5,0,0,3,1,4]
輸出: 6
解釋: 在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3 。
     隨後，在第 7 天（股票價格 = 1）的時候買入，在第 8 天 （股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3 。

示例 2:

輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接連購買股票，之後再將它們賣出。   
     因為這樣屬於同時參与了多筆交易，你必須在再次購買前出售掉之前的股票。

示例 3:

輸入: [7,6,4,3,1] 
輸出: 0 
解釋: 在這個情況下, 沒有交易完成, 所以最大利潤為 0。

題目解析

這裏限制了最多兩筆交易。

狀態

有 第一次買入（fstBuy） 、 第一次賣出（fstSell）、第二次買入（secBuy） 和 第二次賣出（secSell） 這四種狀態。

轉移方程

這裏最多兩次買入和兩次賣出，也就是說 買入 狀態之前可擁有 賣出 狀態，賣出 狀態之前可擁有 買入 狀態，所以買入和賣出的轉移方程都需要變化。

• fstBuy = max(fstBuy ， -price[i])
• fstSell = max(fstSell，fstBuy + prices[i] )
• secBuy = max(secBuy ，fstSell -price[i]) (受第一次賣出狀態的影響)
• secSell = max(secSell ，secBuy + prices[i] )

邊界

• 一開始 fstBuy = -prices[0]
• 買入后直接賣出，fstSell = 0
• 買入后再賣出再買入，secBuy - prices[0]
• 買入后再賣出再買入再賣出，secSell = 0

最後返回 secSell 。

代碼實現

class Solution {
    public int maxProfit(int[] prices) {
        int fstBuy = Integer.MIN_VALUE, fstSell = 0;
        int secBuy = Integer.MIN_VALUE, secSell = 0;
        for(int i = 0; i < prices.length; i++) {
            fstBuy = Math.max(fstBuy, -prices[i]);
            fstSell = Math.max(fstSell, fstBuy + prices[i]);
            secBuy = Math.max(secBuy, fstSell -  prices[i]);
            secSell = Math.max(secSell, secBuy +  prices[i]); 
        }
        return secSell;

    }
}

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

※南投搬家前需注意的眉眉角角，別等搬了再說!