用python實作動态規劃算法

動态規劃（Dynamic Programming，DP）是一種常用的算法思想，通常用于解決具有重疊子問題和最優子結構性質的問題。動态規劃算法通常是将問題分解為子問題，先解決子問題，再由子問題的解推導出原問題的解。

動态規劃算法的基本步驟如下：

1. 确定狀态：定義狀态變量，表示問題的子問題和解。
2. 确定狀态轉移方程：描述子問題的解和原問題的解之間的關系。
3. 确定初始狀态：狀态轉移方程需要用到的最小子問題的解。
4. 确定計算順序：根據狀态轉移方程，确定子問題的計算順序。

5. 計算問題的解：按照計算順序，依次計算子問題的解，最終得到原問題的解。

   下面以求解斐波那契數列為例，解釋動态規劃算法的應用。

斐波那契數列是一個遞歸定義的數列，第 n 項為前兩項之和，即：

初始值為：

可以使用動态規劃算法計算斐波那契數列，以下是一個使用動态規劃算法的 Python 實作：

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

這個實作中，我們定義了狀态變量 dp，表示斐波那契數列的前 n 項。初始狀态為 dp[0] = 0 和 dp[1] = 1。然後我們通過循環計算每一項的值，直到得到第 n 項的值。

使用動态規劃算法計算斐波那契數列的時間複雜度為 O(n)，因為我們需要計算前 n 項的值。使用動态規劃算法，可以大大降低計算斐波那契數列的時間複雜度，避免重複計算。

可以直接調用 fibonacci 函數來計算斐波那契數列的第 n 項。例如，計算斐波那契數列的第 10 項，可以這樣調用：