前言
最近有小夥伴在後臺留言說，可不可以聊一聊動態規劃。這是一個有趣的話題，因為對於大部分業務型公司來說，面試中的算法部分並不會考這一塊。但是BAT等一線網際網路公司又不一定不會考，比如我在面試頭條的時候就被問了一道動態規劃的題目。
此外，我個人覺得動態規劃有趣的原因是，我認為應用層的工程師能接觸到或者用到的「最需要思考」的算法題目了。所以咱們今天就好好聊一聊動態規劃。
正文
一、貪心算法
聊動態規劃之前，我想先聊一聊貪心算法。
1.1、什麼事貪心算法
一個很經典的題目：我們手裡有1元、5元、10元、50元面值的若干紙幣。我們需要用最少張數拿正好66元錢。我們應該怎麼拿？
在這樣的給定條件下，我們採用每次拿面值最大，直到湊夠66元的策略：1張 * 50元 + 1張 * 10元 + 1張 * 5元 + 1張 * 1元。那麼此時正巧達成題目中的答案。OK，這種策略我們都知道叫做：「貪心」。
1.2、貪心算法的弊端
貪心算法在一定條件下的確能夠得出我們想要的結果。當然我們也很清楚，在一定條件下，貪心算法也並不能得到我們想要的結果。比如：在1元、5元、11元面值的前提下，拿最少張數湊出15元。
在貪心算法的策略下：1張 * 11元 + 4張 * 1元。但是3張 * 5元明顯可以做到更優。
我們很清楚貪心算法的問題出在哪：貪心算法每次會都選擇當前情況下的最優解。但是有時一味地只看重「眼前的利益」，並不一定會「笑到最後」。
貪心算法就是最真實的例子。
1.3、能否改進
既然我們明白貪心算法錯就錯在：每一步只考慮了當下最優解。那麼換個角度來說，是不是只要我們每一步考慮全局最優解就能解決這個問題。
可是轉念一想，每一步考慮全局最優解似乎不大可能。
的確我們想每一步都做到全局最優解的確是不可能。但我們可以換一種思路：我們可以去讓未來告訴我們答案。
這種思想就是動態規劃。
二、動態規劃
2.1、暴力破解？
還是剛才那個題目：在1元、5元、11元面值的前提下，拿最少張數湊出15元。
對於我們來說，我們的任務就是：每一次從1元、5元、11元的錢幣中拿出一張，最少在第幾次拿完湊出了15元。
所以這個問題可以用一張圖來表示：
我們會發現，對於當前的我來說：我除了知道我還需要湊多少錢，以及我拿了幾張錢幣以外我什麼都不清楚（既然如此，我還考慮個屁最優解！）。所以既然我們根本不能提前知道接下來會怎麼樣，那我們就把這個難題交給下一步…因為最後一步終究會湊出15元…我猜小夥伴們讀到這，已經開始罵娘了…tm的，我也明白可以這麼做啊。不就是暴力破解嗎！
2.2、非也
咱們來模擬一下，這裡所謂的「暴力破解」：
情況1：假設第一步我拿了11元，我還需要4元，那麼第二、第三、第四、第五步我只能依次拿1元。最終拿了5張。情況2：假設第一步我拿了5元，我還需要10元，此時我沒辦法拿11元；所以第二步可以選擇拿5元/1元，而第三步也是如此。最好的選擇拿3張5元，最終拿了3張。情況3：假設第一步我拿了1元，我還需要14元，那麼此時擺在我面前的選擇：可以拿11元，也可以拿5元，也可以拿1元。因此對於情況3，我們有更多的選擇去嘗試…假設你嘗試完了所有選擇，你會發現最終拿了5張。此時，不知道大家發沒發現一個現象：對於當下的我來說，當下已經不重要了，因此此時無論怎樣我都會選擇一張錢幣。而真正有意義的操作意味未來我該怎麼選。如果未來的我拿了最少的張數，那麼對我當下的我來說選擇哪個都不重要！
那麼此時，如果我們用函數去表達情況3：定義一個f(n)，表示湊n塊錢最少需要拿幾張。對於情況1來說，第一步的函數表達式：f(15) = min(f(15-11) , f(15-5) , f(15-1)) + 1。
這裡的含義：第一步我隨便拿，我只需要保證我拿完之後，接下來拿的張數最少即可。也就是說我不考慮這一步我是拿了11元，還是5元，還是1元。我只關心我拿完之後接下來最少就好，也就是min(f(15-11) , f(15-5) , f(15-1))->min(f(4) , f(10) , f(14))。
而min(f(4) , f(10) , f(14))又可以分別演化成：
f(4) = min(f(4-1))f(10) = min(f(10-5) , f(10-1))f(14) = min(f(14-11) , f(14-5) , f(14-1))所以我們只關心f(n)，至於是f(n-11)還是f(n-5)還是f(n-1)，我們統統不關心！
2.3、實現
我猜認真思考的小夥伴已經大概明白了這題的思路。這裡貼一個有意思的反向解題代碼，大家加深一下印象：
private lateinit var moneyRecord :IntArray // 這個數組的每個下標存儲：湊足0-n面值的錢，最少使用拿幾張private val coins = intArrayOf(1, 5, 11) // 面值fun funtion(curMoney: Int, allMoney: Int) { // curMoney：當前需要湊的面值，從0開始跌增到allMoney（最終需要湊的面值，也就是15） if (curMoney == 0) { moneyRecord[curMoney] = 0 funtion(curMoney + 1, allMoney) } else { var min = 9999999 // 初始化一個很大的數值。當最後如果得出的結果是這個數時，說明湊不出來。 // 在1、5、11面值中，最少次數能夠湊齊curMoney面值 for (coin in coins) { if (curMoney >= coin && moneyRecord[curMoney - coin] + 1 < min) { min = moneyRecord[curMoney - coin] + 1 } } moneyRecord[curMoney] = min // 遞歸 if (curMoney < allMoney) { funtion(curMoney + 1, allMoney) } }}2.4、總結
動態規劃與暴力破解的區別在哪裡：
暴力破解明顯的特徵，我們需要考慮到所有的邊界條件，這樣帶來的問題就是if特別的多。
而動態規劃所有的邊界條件就是一共有幾種可能。對於動態規劃來說，我們只關係結果，並不關心結果是怎麼算出來的。譬如，求出f(15)，只需要知道f(14),f(10),f(4)的值。其他信息並不需要。所以我們就可以將其簡化和相同問題的遞歸。
也就是「學術界」為其總結的倆個性質：
無後效性最優子結構而這就是動態規劃。
尾聲
最近真的忙…忙的都想離職了。不爽！哈哈，但是生活還是要繼續~~衝鴨！