??作者介紹：10年大廠數(shù)據(jù)\經(jīng)營分析經(jīng)驗，現(xiàn)任大廠數(shù)據(jù)部門負(fù)責(zé)人。
會一些的技術(shù)：數(shù)據(jù)分析、算法、SQL、大數(shù)據(jù)相關(guān)、python

歡迎加入社區(qū)：碼上找工作
作者專欄每日更新：

LeetCode解鎖1000題: 打怪升級之旅
python數(shù)據(jù)分析可視化：企業(yè)實戰(zhàn)案例
備注說明：方便大家閱讀，統(tǒng)一使用python，帶必要注釋，公眾號 數(shù)據(jù)分析螺絲釘 一起打怪升級

動態(tài)規(guī)劃（Dynamic Programming, DP）是解決優(yōu)化問題的一種算法策略，它將一個復(fù)雜問題分解為更小的子問題，通過解決子問題來逐步找到復(fù)雜問題的最優(yōu)解。動態(tài)規(guī)劃適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。接下來，我們通過一個經(jīng)典的動態(tài)規(guī)劃問題——斐波那契數(shù)列（Fibonacci Sequence）來詳細(xì)介紹動態(tài)規(guī)劃的思路和實現(xiàn)步驟。

問題定義

斐波那契數(shù)列是這樣一個序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …，其中每個數(shù)字（從第三個數(shù)字起）都是前兩個數(shù)字的和。斐波那契數(shù)列的定義如下：

我們的目標(biāo)是編寫一個函數(shù)，輸入n，輸出斐波那契數(shù)列的第n項。

1. 遞歸解法（非DP解）

首先，我們嘗試使用遞歸解法，這種方法簡單直觀，但效率較低。

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

這個遞歸解法雖然簡單，但它進(jìn)行了大量重復(fù)計算，時間復(fù)雜度為O(2^n)。?

我們可以通過分析斐波那契數(shù)列的遞歸樹來直觀地看出重復(fù)計算的發(fā)生。

斐波那契數(shù)列的遞歸樹

考慮計算F(5)的過程，遞歸樹如下所示：

在這個樹狀結(jié)構(gòu)中，每個節(jié)點表示一個遞歸調(diào)用，節(jié)點的值是調(diào)用的參數(shù)。從這個樹中我們可以觀察到：

1. 重復(fù)的子問題：F(3)、F(2)、F(1)和F(0)被計算了多次。特別是F(2)，在整個計算過程中被重復(fù)計算了三次。

2. 增長的遞歸調(diào)用：隨著參數(shù)n的增加，遞歸調(diào)用的數(shù)量呈指數(shù)級增長。例如，F(n)的計算會導(dǎo)致F(n-1)和F(n-2)的計算，而這些調(diào)用又會分別導(dǎo)致更多的遞歸調(diào)用。

分析重復(fù)計算的原因

重復(fù)計算的主要原因在于，遞歸解法中對每個子問題的解決都是獨立進(jìn)行的，它沒有考慮到在求解過程中，很多子問題實際上是相同的。由于遞歸方法沒有記錄已經(jīng)解決的子問題的結(jié)果，每次遇到這些子問題時，它都會重新進(jìn)行計算。

2. 動態(tài)規(guī)劃解法

為了提高效率，我們使用動態(tài)規(guī)劃的方法，避免重復(fù)計算。

步驟1：定義狀態(tài)

定義dp數(shù)組，其中dp[i]表示斐波那契數(shù)列中第i個數(shù)的值。

步驟2：確定狀態(tài)轉(zhuǎn)移方程

根據(jù)斐波那契數(shù)列的定義，我們可以得到狀態(tài)轉(zhuǎn)移方程：dp[i] = dp[i-1] + dp[i-2]

步驟3：確定初始條件和邊界條件

dp[0] = 0, dp[1] = 1

步驟4：計算順序

從小到大計算dp數(shù)組的值。

動態(tài)規(guī)劃代碼實現(xiàn)

def fibonacci_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

這種方法的時間復(fù)雜度為O(n)，空間復(fù)雜度也為O(n)。

3. 動態(tài)規(guī)劃優(yōu)化

對于斐波那契數(shù)列問題，我們實際上不需要保存整個dp數(shù)組，只需要保存前兩個狀態(tài)即可。

優(yōu)化后的代碼

def fibonacci_dp_optimized(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for i in range(2, n+1):
        prev, curr = curr, prev + curr
    return curr

這個優(yōu)化后的版本將空間復(fù)雜度降低到了O(1)。

4. 算法思考

1. 子問題

在動態(tài)規(guī)劃中，我們將原問題分解為較小的、相互關(guān)聯(lián)的子問題。對于斐波那契數(shù)列問題，求F(n)可以看作是一個原問題，它可以分解為求F(n-1)和F(n-2)兩個子問題。而F(n-1)和F(n-2)又可以繼續(xù)分解，直到F(1)和F(0)。

2. 重疊子問題

動態(tài)規(guī)劃適用于那些有大量重疊子問題的情況，即不同的問題求解路徑中包含了許多相同的子問題。在遞歸求解斐波那契數(shù)列時，F(n-1)和F(n-2)會重復(fù)計算F(n-3)、F(n-4)等更小的子問題。動態(tài)規(guī)劃通過記憶化（存儲）這些子問題的解來避免重復(fù)計算。

3. 最優(yōu)子結(jié)構(gòu)

斐波那契數(shù)列問題具有最優(yōu)子結(jié)構(gòu)的特點，即問題的最優(yōu)解包含了其子問題的最優(yōu)解。雖然斐波那契數(shù)列問題本身不涉及“最優(yōu)化”，但其解決方法體現(xiàn)了最優(yōu)子結(jié)構(gòu)的思想：F(n)的最優(yōu)解（即準(zhǔn)確解）可以通過組合F(n-1)和F(n-2)的解得到。

4. 動態(tài)規(guī)劃表（DP Table）

在這個例子中，dp數(shù)組就是所謂的動態(tài)規(guī)劃表。它用來記錄每一步的結(jié)果（即每個F(i)的值），以便于后續(xù)的計算可以直接引用前面的結(jié)果，而不是重新計算。這種方法極大地提高了效率，因為每個子問題只被解決一次，并且一旦被解決，其結(jié)果就會被保存。

5. 狀態(tài)轉(zhuǎn)移方程

動態(tài)規(guī)劃的核心是狀態(tài)轉(zhuǎn)移方程。在斐波那契數(shù)列的例子中，狀態(tài)轉(zhuǎn)移方程是dp[i] = dp[i-1] + dp[i-2]。這個方程描述了問題狀態(tài)之間的關(guān)系，即如何從已知的子問題的解得到當(dāng)前問題的解。

通過這個斐波那契數(shù)列的例子，你可以看到，盡管我們使用的是簡單的數(shù)組來存儲每一步的結(jié)果，但這個過程完全體現(xiàn)了動態(tài)規(guī)劃的思想：分解問題、解決子問題、存儲子問題的解以避免重復(fù)計算。這就是dp數(shù)組與動態(tài)規(guī)劃思想關(guān)聯(lián)的方式，它是實現(xiàn)動態(tài)規(guī)劃策略的一個工具。

總結(jié)

動態(tài)規(guī)劃中的應(yīng)用體現(xiàn)了動態(tài)規(guī)劃的核心思想：存儲中間結(jié)果，避免重復(fù)計算。這里的dp數(shù)組正是用來存儲每個子問題的解，即斐波那契數(shù)列中每個位置的數(shù)值。讓我們更深入地理解它與動態(tài)規(guī)劃思想的關(guān)聯(lián)：文章來源地址http://www.zghlxwxcb.cn/news/detail-852633.html

到了這里，關(guān)于解鎖動態(tài)規(guī)劃：從斐波那契到高效算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！