今天是算法與數據結構專題的17篇文章，也是動態規劃專題的第6篇。
今天我們一起來看一道非常經典的動態規劃的問題，有多經典呢？我想了一下，大概是我這輩子做的最早的一道動態規劃問題，以至於我現在都記得它的題面。
題面
這道題就是導彈攔截系統，說是某一個國家開發了一套導彈攔截系統，這個攔截系統可以攔截敵國打來的導彈。不同射程的導彈在彈射出去的時候的飛行高度都不同，這個攔截系統可以從低到高攔截飛來的導彈，但是它下一次攔截的高度必須大於等於上一次高度，只能升高不能降低。那麼請問，假設我們檢測到了所有敵國發射的導彈飛行的高度，請問我們最多可以攔截其中多少枚？
上面講題意講了這麼多，其實用一句話就概括了，就是求一個序列當中
最長不下降子序列的長度。也有題目反過來求最長不上升子序列，意思是一樣的。暴力解法
我們來看一個例子，假設敵國一共發來了8枚導彈，它們的飛行高度分別是：[65, 158, 170, 299, 300, 155, 207, 389]。
我們用眼睛看看還是蠻容易找出答案的，答案應該是[65, 158, 170, 299, 300, 389]一共6枚導彈，其中的155和207無法攔截。假設我們不知道這是一個動態規劃算法，我們怎麼想出解法呢？
還是老規矩，我們先從最簡單的暴力方法開始思考。最暴力的方法就是枚舉這n個數所有可能出現的狀態，對於其中的每個元素而言，都有兩種狀態，一種是拿取，一種是不拿。那麼對於一個n個元素的數組而言，顯然一共會有 2^n 個不同的可能。然後我們再依次判斷每一種可能性是否合法，保留合法的長度最大的那一個。
當然我們也可以用搜索來做，我們可以在搜索的過程當中排除掉非法的組合，但在極端情況下，比如整個數組升序的時候，那麼還是會枚舉到所有的情況，那麼整體的複雜度依然是 2^n 。這顯然是我們不能接受的。
那我們怎麼來找到更好的解法呢？
感性的認識
我們觀察和思考一下這個問題，我們會發現在這個問題當中，不同規模的解法應該都是一樣的。如果某種方法可以解出長度為1000的序列，那麼自然也可以解出長度為5的序列，反之也是一樣。所以我們不由地可以想到，那我們從最簡單的情況開始入手，能不能找到解法呢？
我們從長度為1的數組開始，顯然答案是確定的，就是1.
如果長度是2呢？比如[65, 158]，那麼我們需要判斷一下第二個數能否跟在第一個數後面，也就是說第二個數是否大於等於第一個數，如果成立的話，那答案就是2，否則答案還是1，比如[65, 34]，最長的序列就只能是[65]或者[34]。
那如果是3個數呢？情況會複雜一點，我們可以反過來分析，如果答案是3，那麼只有一種情況就是序列是遞增的，如果答案是2，那麼就有兩種情況，一種是前面兩個元素構成遞增比如[20, 30, 10]，第二種情況是前面兩個元素之中的一個和第三個數構成遞增，比如[10, 5, 30]或者是[10, 5, 8]。也有可能答案是1，當序列是遞減的時候。
表面上看我們什麼也沒有發現，並沒有找出一個好的方案來解決問題，但是其實已經有一個很重要的結論擺在了我們面前——這個最長不下降的序列並不一定包含最後一個元素。
看起來這似乎是廢話，答案當然可能不包含最後一個元素，因為如果最後一個元素非常小，它顯然不可能組成很長的序列。但是反過來看，我們的結論會整個顛覆。既然答案並不一定以最後一個元素結尾，而序列必須有一個結尾，而目前我們沒有結論證明某一個節點會不能作為結尾。所以我們自然地得出結論，所有位置都有可能是答案的結尾。
這個其實很好證明，我們來看下面這張圖：
在這個序列當中，a1, a2到ai遞增，從ai+1開始遞減，並且 ai+1 < a1，那麼顯然[a1. a2,...,ai]就是答案，也就是說ai就是答案的結尾。只要我們改變i的值，就可以讓答案的結尾出現在不同的位置。所以理論上來說數組當中的每一個位置都可能是答案的結尾。
從這個結論出發我們可以得到另一個結論，既然所有位置都可能是最終答案的結尾，我們想要找到答案就需要遍歷所有的結尾，也就是所有的位置。而且對於一個確定的位置而言，以它為結尾的最長不下降子序列必然也是確定的（可能有多種情況）。所以到這裡，我們經過了一系列的推導，得出了一個結論，我們需要求解所有位置的答案，然後從其中選擇整體上最優的那個。
這是一個很感性很直觀的認識，但是離答案已經不遠了，我們再加上一些理性的分析即可。
理性的分析
我們整理一下剛才的結論和思路，我們知道了我們要求解每一個位置的答案，然後從其中找到一個整體最優的。假設我們想要知道i位置結尾的答案，這其實意味著我們放棄了i位置後面所有的元素。我們考慮的序列只剩下了i以及i之前的部分。
我們來看下面這張圖：
我們列舉了一個長度等於5的數組的答案，我們遍歷了所有的i，每一個i都對應num[:i]這個數組的答案。每一個i都可以看成是一個獨立的問題，我們要做的就是求出每一個i對應的答案。
既然我們要求出每一個i的答案，那麼我們能不能利用之前已經求出的結果來加速計算過程呢？推導到這裡整個動態規劃的思路已經非常清楚了。
我們假設，我們已經知道了所有小於等於i的答案，我們現在要求i+1的答案，應該怎麼做呢？
很簡單，我們遍歷所有小於等於i的j，如果 aj 小於等於 ai+1，那麼說明 ai+1 可以跟在aj的後面，構成一個解。如果我們用dp數組來存儲所有位置的答案，那麼我們可以得到下面這個轉移方程：
轉移方程列出來之後就很簡單了，我們從最小的i開始，利用前面的結果來計算每一個i對應的答案，然後從其中找出最大的作為整體的解即可。我們來看下代碼，查看更多細節：
這段代碼非常短，只有兩重循環，結合之前的描述應該很容易理解。我們複雜度分析也很簡單，從兩重循環入手的話，我們顯然是 O(n^2) 。我們也可以從狀態數和決策數入手，我們每一個結尾的答案是狀態，數量是n。對於每一個狀態而言，它有可能跟在面面的每一個位置後面，所以潛在的決策數最壞也是n，所以整體的複雜度是 O(n^2) 。
雖然我們花費了很多筆墨，但是這個算法並不困難，的確是高中生競賽的難度。但彆著急，問題還沒有結束，我們的下一個問題是，這個算法還有改進的空間嗎?
進階
既然這個問題問出來，顯然答案是確定的。如果你在面試當中被面試官問還能有優化嗎，你要是答沒有，那可是會扣很多分的。面試官不是覺得你太魯莽了就是覺得你情商捉雞，所以如果面試的時候被問題，一定要回答有，至於怎麼優化，那可以慢慢想，答不對都沒問題，要是基調就定錯了，可是很嚴重的。
動態規劃問題的優化其實只有兩種情況，要麼從狀態數入手，減少多餘的狀態數，要麼從決策入手，快速找出正確的決策。比如之前介紹的單調優化就是後者，一般情況下來說狀態數都是比較固定的，也是很難減少的，往往優化都要從決策上入手。這題也不例外，那麼我們怎麼來優化呢？
想要優化，眼前的信息是不夠的，算法都不是憑空想出來的，往往是推導出來的。我們還需要更多的信息和結論才行，對於每一個要求的i+1位置而言，我們已經知道了它前面所有答案的情況。如果我們可以設計一個方法，快速地找到i+1究竟應該跟在哪個位置後面就好了。
這個方法我們幹想是想不到的，必須要結合數據。我們用上面的樣例來舉例，畫出所有位置最佳的轉移決策：
好像也看不出什麼眉目來，我們隨意挑出一個元素來仔細查看，假設我們就挑選207。我們列舉出207之前所有的位置的元素和答案，並且按照元素大小進行排序，可以得到這樣的結果：
其中的155和158的長度都是2，顯然我們可以去除掉158，只保留155。因為155 < 158，155能轉移到的位置158一定也可以。我們把這個結論推廣，也就是說
對於長度相同的位置，我們只需要保留其中最小的那個。我們觀察上面這個序列，好像數字越大的長度也就越大，長度越大的數字也就越大，但真的是這樣嗎？我們試著更改一個值：
我們把158改成358，好像就不滿足了，雖然358很大，但是它的答案很小。但是當我們根據上面的原則去重之後，我們
剩下的序列還是遞增的。這個只是巧合還是的確如此呢？我們可以試著證明一下，假設存在反例。我們假設數組當中存在兩個數x和y，這兩個數同時存在於去重之後的答案數組當中。其中x < y，並且x的答案大於y。根據我們剛才排序的邏輯，那麼x應該排在y的左側。數組當中比x小的那些值必然也出現在x的左側，那麼必然存在一個位置的答案和y相等並且數值小於y，那麼y必然會被去除，所以就和x和y同時存在矛盾了。
我們用下圖來展示一下上面列舉的反例。
也就是說對於我們經過處理之後得到的這個dp數組當中的元素必然是遞增的，所以，其中每一個元素所在的位置其實就代表這個元素對應的長度。比如上圖當中2排在數組當中的第二位，那麼就說明2這個數字對應的答案是2。
我們更新dp數組的過程主要做了兩件事，第一件事是讓dp數組當中的元素儘量多，我們每次都會把最大的數插入dp的末尾。另外一件事情就是讓dp數組當中的每個位置的元素儘量小。這樣才可以為只有插入儘可能多的元素做準備，如果前面的數就特別大，那後面就沒辦法傳入其他數了。
比如上圖當中的3和9的答案都是3，但是顯然3比9更好，因為3能夠達到答案3，說明出現在3右側的只要大於3的數至少可以獲得4的長度。我們既可以理解成3對應的答案是3，也可以理解成答案3對應的最小滿足的數是3，而不是9。
由於dp數組當中的元素有序，我們可以使用二分法來找到對應更新的位置，從而可以保證我們可以在logN的時間內找到最佳決策。那麼整體的複雜度就變成了狀態數是n，決策數是logN，最後的複雜度就是 O(nlogn) 。
我們來看下代碼：
總結
到這裡，這道題就講解完了，整個題目的精髓在於我們維護了一個有序的數組，使得我們可以通過二分查找來找到每個狀態的最佳決策。說來慚愧這道題我做過好幾次，但是之前很多次都記不住解法，過段時間就會忘記，後來我才找到了訣竅。我們不能死記算法運行的原理，這樣下次遇到了變體我們也做不出來。我們必須要理解這個優化出現的原因，推導的前因後果，這樣我們才有能力推導其他的問題。
所以希望大家都能把這個推導的過程想明白，而不是隻停留在我們怎麼運用二分進行優化上。關於這道題還有其他的變種，舉個例子，比如如果我們想要求出最少需要幾套導彈系統能夠攔截所有的導彈，應該怎麼做呢？這個問題留給大家思考。我想如果能能夠理解上面的做法，應該不難想出答案。
今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
閱讀更多 承志的算法課堂 的文章
