前言

算法店展，對于初級程序員(Api Caller) 而言,可能并不怎么重要渐逃，因為平時工作中壓根用不到算法伐谈。但是要進入高級工程師烂完，就要知道，如何用最優(yōu)的計算方式來完成同一件任務诵棵。比如抠蚣，騰訊面試經(jīng)常問到的，給你一個億的用戶數(shù)據(jù)履澳，要你從中找到指定的用戶信息嘶窄，如何達到最快怀跛，又或者，手機QQ本地聊天記錄中有1W條數(shù)據(jù)柄冲，如何最快找到包含搜索關鍵字的聊天記錄吻谋，這些都是直接影響到用戶體驗的功能，又比如现横，滴滴打車app漓拾，如何進行最優(yōu)的派單方案，讓所有的注冊車輛都有訂單等等.諸如此類的問題戒祠，Api Caller 的程序員何以解決骇两，拿不到高薪，是有自身的原因的姜盈，誰讓你對高級算法一無所知低千。

算法，基于數(shù)學馏颂，應用于生活中的各種實際問題栋操，它是一個巨大的知識體系，深不可測饱亮，僅以一文概論矾芙，不現(xiàn)實。本文詳解的是近上，動態(tài)規(guī)劃算法剔宪，一種解決問題的通用套路，學會了套路壹无，相當于入了門葱绒，遇到任何問題都可以嘗試套用框架,唯一不足的就是深度和廣度的不足，多訓練就會有提升斗锭，遇到再難的問題也不至于抓耳撓腮地淀，不知所措。

所謂動態(tài)規(guī)劃算法

以下是來自百度百科的概念岖是，經(jīng)我整理之后帮毁，濃縮如下：

動態(tài)規(guī)劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學方法. 提到數(shù)學豺撑，可能很多人都要頭疼了烈疚，讀大學的時候最怕的就是高等數(shù)學，線性代數(shù)聪轿，解析幾何這種爷肝。但是，實際上，動態(tài)規(guī)劃算法灯抛，在現(xiàn)實生活中很多方面都已經(jīng)應用到實踐金赦，比如，求地圖上兩個地點的最短路線对嚼，求資源的最合理分配方案夹抗，以及最優(yōu)排序算法等問題上。按照動態(tài)規(guī)劃的套路猪半，基本上可以做到一套思維框架兔朦，放之四海皆準，每一種問題的之間的差別磨确，都只是前提條件的不同沽甥，以及最終目標的不同。

能夠用動態(tài)規(guī)劃算法解決的問題乏奥，往往都會存在一個"狀態(tài)轉移方程式"摆舟。也就是，在多個不同的階段邓了，所采取的當前決策恨诱。把所有決策整合起來形成一個統(tǒng)一的數(shù)學方程式。

骗炉？照宝？？什么玩意句葵？我們還是說點人話吧

動態(tài)規(guī)劃算法厕鹃，都有一個共同點，那就是求 "最值" 乍丈，像最"短"路徑剂碴，最"少"耗時，最"少"次數(shù)等轻专。這種算法是一種普適性套路算法忆矛，它針對所有求最值得問題，都可以用一個統(tǒng)一的思維方式去解決请垛。

狀態(tài)轉移方程催训，其實也就是一個所謂的 數(shù)學函數(shù)公式(能當程序員，數(shù)學應該是都不錯的,你肯定知道我在說什么 ^-叼屠！)瞳腌，比如下文即將講到的 斐波拉契數(shù)列公式。

寫出狀態(tài)轉移方程之后镜雨，就可以開始用程序代碼來解決實際問題。本文采用的編程語言是Kotlin,但是我都有些詳盡的注釋，就算不懂Kotlin荚坞，閱讀起來應該也不會有太大障礙挑宠。

開始這一切之前，有一些算法的相關概念在此聲明颓影。

時間復雜度和空間復雜度

一個大的問題各淀，往往可以分解成若干個子問題，大事化小诡挂，小事化了碎浇。

時間復雜度 = 子問題的個數(shù) x 解決一個子問題所需的時間
空間復雜度 = 子問題的個數(shù) x 解決一個子問題所需的內存空間

時間復雜度 描述算法的執(zhí)行效率。常見的時間復雜度有O(1),O(log₂n),O(n),O(n^2). n表示子問題的個數(shù)璃俗，分別表示0次方奴璃，1/2次方，1次方城豁，和2次方苟穆。次數(shù)越高，復雜度越大, 解決同樣的問題花費的時間就越長唱星，算法的效率也就越低雳旅，誰都不希望自己的程序運行效率低。

空間復雜度 描述算法占用內存间聊。越高攒盈，說明算法占用的內存空間越大。它的寫法和時間復雜度一樣哎榴，次數(shù)越高型豁，算法占用的空間也就越大，耗費內存就越大叹话，無論是服務器上的程序算法偷遗，還是手機上的程序算法，都會考慮內存的問題驼壶。

時間和空間復雜度都只是描述算法的復雜程度氏豌，一般對比只看大概數(shù)字級別，而不是去糾結實際的耗時热凹，比如3ms泵喘，6ms 級別上相差不大的基本也就是同一個時間復雜度。

遞歸回調

遞歸般妙，也就是函數(shù)對自身的調用纪铺，一般都會設定一個退出遞歸的條件，防止無限回調碟渺。動態(tài)規(guī)劃鲜锚，大問題分解成小問題，一般都會用到遞歸調用。

初識動態(tài)規(guī)劃：斐波拉契數(shù)列

著名的斐波拉契數(shù)列, f(1) = f(2) = 1,往后的f(n) 都是前面兩個數(shù)的和芜繁，寫成數(shù)學公式旺隙，也就是所謂"狀態(tài)轉移方程"，如下：

image-20200422151048373.png

如果我們要得到一個 f(40)骏令，斐波拉契數(shù)列上位置40的函數(shù)值蔬捷。我們可以完全按照數(shù)學公式來寫代碼。

暴力解法

利用遞歸算法來編程就是如下寫法：

fun fib1(x: Int): Long {
    return if (x == 1 || x == 2) {
        1
    } else
        fib1(x - 1) + fib1(x - 2)
}

如果用上面的算法來計算斐波拉契數(shù)列中某個節(jié)點的值榔袋，我們來算算時間復雜度是多少周拐。

如果是f(40),那么遞歸樹結構就是：

image-20200501155359273.png

時間復雜度

子問題的個數(shù)

每個子問題都會分裂成2個子問題。所以子問題的個數(shù)是 2ⁿ
一個子問題耗費的時間

一個子問題只需要一次加法凰兑。所以妥粟，解決一個子問題的時間是1

合并起來，時間復雜度就是O(2^n) 指數(shù)級別的復雜度聪黎，效率極低罕容。

空間復雜度（O(1)）這里不談，因為都是臨時變量稿饰，不存在永久保存的數(shù)據(jù)锦秒。

測試一下執(zhí)行的效率:

fun main() {
    val start = System.currentTimeMillis()
    fib1(40)
    val end = System.currentTimeMillis()
    println("${(end - start)}ms")
}

結果（受系統(tǒng)的調度影響，多次運行結果可能不同喉镰，但是數(shù)量級應該是一樣的）：

311ms

從上面的圖可以看出旅择，很多子問題都是重復計算的。比如f(38),f(37)...這就是上面的算法所帶來的低效率問題侣姆，在做很多不必要的重復性工作生真。那么有沒有辦法避免這種重復的遞歸計算呢？

一重改進

既然上面的f(37),f(38)等都在重復計算捺宗，那么我們用一個備忘錄map柱蟀，記錄已經(jīng)計算出的結果。

比如把上面的f(38)的值用map記錄下來蚜厉，下次需要計算的時候长已，直接取值,而不是再去計算

程序變成這樣：

fun fib2(x: Int): Long {
    if (x < 1) return 0
    val map = HashMap<Int, Long>()
    return helper(map, x)
}

fun helper(map: HashMap<Int, Long>, x: Int): Long {
    if (x == 1 || x == 2) return 1
    if (map[x] != null && map[x] != 0L) //如果已經(jīng)計算過了，那就是說保存過了昼牛，就直接返回
        return map[x]!!
    // 否則术瓮，就計算之后再保存
    map[x] = helper(map, x - 1) + helper(map, x - 2) // 這里依然是遞歸
    return map[x]!!
}

fun main() {
    val start = System.currentTimeMillis()
    fib2(40)
    println("${System.currentTimeMillis() - start}ms")
}

運行結果(受系統(tǒng)的調度影響，多次運行結果可能不同贰健，但是數(shù)量級應該是一樣的)：

3ms

執(zhí)行耗時從 三位數(shù)變成了1位數(shù)

這種解法的時間復雜度該如何計算胞四？

子問題的個數(shù)

上面的做法，顯然就是f(38)等這種重復性計算不再存在伶椿，所以可以理解為：當需要f(38)的時候辜伟，會優(yōu)先從 map中去取氓侧。所以，計算出f(40)游昼，也就最多有40個子問題甘苍。所以 f(n)子問題的個數(shù)是 n,
一個子問題耗費的時間

依然只需要一次加法就能算出一個子問題的結果,所以耗時 1

所以時間復雜度是 O(n) , 對比前面一種解法的O(2ⁿ)簡直就是降維打擊尝蠕。

而空間復雜度：

由于這里使用了 map集合來保存已經(jīng)計算出來的值烘豌，所以，空間復雜度：

子問題的個數(shù)

f(n)子問題的個數(shù)還是n
一個子問題耗費的空間

每一個子問題的計算結果都會占用1個空間來保存, 所以一個子問題耗費空間1

所以空間復雜度= O(n)

時間復雜度降低了看彼，程序的運行效率提高了廊佩，但是，空間復雜度卻升高了靖榕，這就是所謂的"空間換時間".

二重改進

不知道有沒有人跟我有一樣的感覺标锄！那就是，這種遞歸算法茁计，自上而下的思維方式有點反人類料皇，容易把人繞暈。如果可以的話星压，我寧愿順著正常人的思維去思考践剂，比如，自下而上娜膘，先得出 f(1),f(2),再得出f(3),f(4)...一直到我們要求的f(40).

程序寫成下面這樣:

fun fib3(x: Int): Long {

    val map = HashMap<Int, Long>() // 初始化一個map

    map[1] = 1
    map[2] = 1

    for (i in 3..x) {
        val pre1 = map[i - 1] ?: 0
        val pre2 = map[i - 2] ?: 0
        map[i] = pre1 + pre2
    }
    return map[x] ?: 0
}

fun main() {
    val start = System.currentTimeMillis()
    fib3(40)
    println("${System.currentTimeMillis() - start}ms")
}

時間復雜度：

子問題的個數(shù)

只是思考的方向反了逊脯，子問題仍然是n個
一個子問題耗費的空間

處理一個子問題的，仍然是一次加法竣贪，時間依然是1

所以時間復雜度依然是：O(n)

空間復雜度:

子問題的個數(shù)

n
處理一個子問題军洼，需要保存一個數(shù)據(jù)，所以占空間是1

空間復雜度為：O(n)

這種算法演怎，把自上而下的遞歸匕争，變成了自下而上的遍歷，時間和空間復雜度都沒有變化爷耀，但是寫法更容易理解甘桑，執(zhí)行效率也如預料中一樣,并沒有變化:

4ms

三重改進

上面一種改進方法，我們用map保存了已經(jīng)計算出來的值畏纲，自上而下遞歸計算扇住，和自下而上遍歷計算，時間和空間復雜度都相同盗胀。但是艘蹋，自下而上的計算依然有優(yōu)化空間。

思考:是否可以不需要map來保存數(shù)據(jù)票灰？

上一節(jié)的改進女阀，f(n)依賴的僅僅是f(n-1)和f(n-2). 而不需要另外的數(shù)據(jù)一直保存宅荤。

/**
 * 最后優(yōu)化
 */
fun fib4(x: Int): Long {
    if (x == 1 || x == 2) return 1L
    var cur = 1L
    var pre = 1L
    for (i in 3..x) {
        val sum = cur + pre
        pre = cur
        cur = sum
    }
    return cur
}

fun main() {
    val start = System.currentTimeMillis()
    fib4(40)
    println("${System.currentTimeMillis() - start}ms")
}

時間復雜度：

子問題的個數(shù)

仍然是 n
一個子問題耗費的時間

一個子問題只需要1次加法，所以耗時 1

所以時間復雜度是O(n)

空間復雜度：

子問題的個數(shù)是n
一個子問題所占用的空間是1浸策，但是都是臨時占用冯键，函數(shù)執(zhí)行完畢之后就會釋放，算法中的臨時變量所占空間并不會累加庸汗，

所以空間復雜度惫确，是O(1)

運行結果,時間耗費上依然沒變：

3ms

至此，斐波拉契數(shù)列問題才算圓滿解決蚯舱，時間和空間復雜度都達到了最優(yōu)改化。

總結

動態(tài)規(guī)劃算法，解決問題的一般思路為：

寫出狀態(tài)轉移方程式
直接按照方程式寫出暴力解法程序枉昏，可能效率會很低
使用集合保存已經(jīng)計算出的子問題的結果陈肛，優(yōu)化子問題的個數(shù)，得出優(yōu)化算法優(yōu)化時間復雜度
使用順序遍歷的思路來替代逆序遞歸兄裂，讓程序代碼更好理解
嘗試能否使用臨時變量替代集合句旱，優(yōu)化空間復雜度

但是，聰明的你們應該已經(jīng)發(fā)現(xiàn)了好像哪里不對晰奖。

沒錯谈撒，最前面說過，動態(tài)規(guī)劃算法畅涂，是用來解決最值問題的算法港华，目的是得出最優(yōu)解。顯然午衰，斐波拉契數(shù)列并不是求最值立宜。從這里可以看出，這種解法思路臊岸，不僅僅針對求最值問題橙数，有一些非此類問題，也可以嘗試使用動態(tài)規(guī)劃去思考帅戒。

本文使用斐波拉契數(shù)列灯帮，是因為它的狀態(tài)轉移方程是公開的，大家入門都很容易理解逻住。但是現(xiàn)實生活中的實際問題钟哥，它的狀態(tài)轉移方程，要根據(jù)實際情況瞎访，分情況列出腻贰，如果方程列錯了，就算算法再精良扒秸，結果也不是我們想要的播演。

所以冀瓦，使用動態(tài)規(guī)劃解決問題，還是萬事開頭難写烤。只要列出了正確的狀態(tài)轉移方程翼闽，后續(xù)，我們才可以按照套路來洲炊，一步一步優(yōu)化算法感局。所以千萬不要瞧不起效率最低的暴力解法，它代表的是最原始的也是选浑，最標準的解法蓝厌。計算結果出現(xiàn)問題，我們首先要審視的就是 狀態(tài)轉移方程是否正確古徒，方程正確，才能去查后面的問題读恃。

下一篇將以一個實際案例(湊零錢問題)隧膘，來一步步展示動態(tài)規(guī)劃算法的實際應用。

算法Balabala動態(tài)規(guī)劃概述