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

前言

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

算法，基于數(shù)學，應(yīng)用于生活中的各種實際問題，它是一個巨大的知識體系，深不可測，僅以一文概論，不現(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īng)用到實踐，比如，求地圖上兩個地點的最短路線，求資源的最合理分配方案，以及最優(yōu)排序算法等問題上。按照動態(tài)規(guī)劃的套路，基本上可以做到一套思維框架，放之四海皆準，每一種問題的之間的差別，都只是前提條件的不同，以及 最終目標的不同。

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

？？？什么玩意？我們還是說點人話吧

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

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

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

開始這一切之前，有一些算法的相關(guān)概念在此聲明。

時間復雜度和空間復雜度

一個大的問題，往往可以分解成若干個子問題，大事化小，小事化了。

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

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

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

空間復雜度 描述算法占用內(nèi)存。越高，說明算法占用的內(nèi)存空間越大。 它的寫法和時間復雜度一樣，次數(shù)越高，算法占用的空間也就越大，耗費內(nèi)存就越大，無論是服務(wù)器上的程序算法，還是手機上的程序算法，都會考慮內(nèi)存的問題。

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

遞歸回調(diào)

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

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

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


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),那么遞歸樹結(jié)構(gòu)就是：

image-20200501155359273.png

時間復雜度

  • 子問題的個數(shù)

    每個子問題都會分裂成2個子問題。所以子問題的個數(shù)是 2n

  • 一個子問題耗費的時間

    一個子問題只需要一次加法。所以，解決一個子問題的時間是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")
}

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

311ms

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

一重改進

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

比如把上面的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")
}

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

3ms

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

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

  • 子問題的個數(shù)

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

  • 一個子問題耗費的時間

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

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

而空間復雜度：

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

  • 子問題的個數(shù)

    f(n)子問題的個數(shù)還是n

  • 一個子問題耗費的空間

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

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

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

二重改進

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

程序?qū)懗上旅孢@樣:

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)

運行結(jié)果,時間耗費上依然沒變：

3ms

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

總結(jié)

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

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

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

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

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

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

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

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。
禁止轉(zhuǎn)載，如需轉(zhuǎn)載請通過簡信或評論聯(lián)系作者。

友情鏈接更多精彩內(nèi)容