庖丁解牛斐波拉契數列和背包問題——詳細決議兩個問題優化程序，帶你從最基本的問題看懂動態規劃！！！

（如果公式不能很好的渲染，請查看這篇同樣內容而且能夠渲染公式的文章）

動態規劃作為一種非常經典的一類演算法，不僅在解決實際問題當中有很多實際的應用，同時通常也是面試的一個重點，本篇文章一步步剖析動態規劃的基本原理，通過斐波拉契數列問題（優化時間復雜度從\(O(2^n)\)到O(n)再到O(log(n))）和經典的01背包問題一步一步帶你從最基本的原理弄懂動態規劃，我們首先分析斐波拉契數列問題，然后在分析問題的時候慢慢的深入動態規劃，

本篇文章的篇章結構：

斐波拉契數列

斐波拉契數列的定義如下：

\[F_0 = 0 \]

\[F_1 = 1 \]

\[F_n = F_{n - 1} + F_{n- 2} \]

就是斐波那契數列由0和1開始，之后的斐波那契數就是由之前的兩數相加而得出，比如說在斐波拉契數列當中第一個數為0，第二個數為1，因此第三個數為前面兩個數之和，因此第三個數為1，同理第四個數是第二個數和第三個數之和，因此第四個數為2，下面就是斐波拉契數的變化：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ....

斐波拉契數列——遞回法

現在我們的問題是要你求第n個斐波拉契數，這個問題還是比較簡單的，很容易想到這就是一個可以遞回解決的問題，在公式\(F_n = F_{n - 1} + F_{n-2}\)當中也容易看出應該使用遞回，現在要確定的就是遞回終止條件，

如果n == 0則回傳0，如果n == 1則回傳1，這就是遞回終止條件，

確定完遞回終止條件之后我們很容易寫出下面這樣的代碼：

public class Fibonacci {

  public static int fibonacci(int n) {
    if (n <= 1)
      return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
  }

  public static void main(String[] args) {
    System.out.println(fibonacci(6));
  }
}

當我們求第6個斐波拉契數的時候，函式fibonacci的呼叫程序如下所示：

我們在呼叫fibonacci(6)的時候他會呼叫：[fibonacci(5)和fibonacci(4)]，然后fibonacci(5)會呼叫[fibonacci(4)和fibonacci(3)]，fibonacci(4)會呼叫[fibonacci(3)和fibonacci(2)]......

我們容易發現我們在函式呼叫的程序當中存在重復，比如下圖兩個相同的部分表示對fibonacci(4)重新計算，因為他們的呼叫樹都是一樣的：

這種使用遞回的方式計算斐波拉契數列的時間和空間復雜度都是\(O(2^n)\)，

斐波拉契數列——陣列法優化時間復雜度

既然是重復計算那么我們是否可用避免重復計算呢？在計算機一種常見的做法就是空間換時間，我們可以將之前計算的資料存下來，比如我們用陣列fib[]存盤我們計算得到的結果，fib[i] = fibonacci(i) ，那么根據斐波拉契數列的公式我們可以知道：

\[fib[i] = fib[i - 1] + fib[i - 2], i \ge 2 \]

當我們通過陣列存盤中間計算的資料的時候，我們應該使用什么樣的演算法進行計算呢？

在上面的圖片當中比如我們要計算綠色框對應的資料，根據公式：

\[fib[i] = fib[i - 1] + fib[i - 2], i \ge 2 \]

我們知道綠色框依賴它前面的兩個資料，因此我們在計算fib[i]的時候，需要提前將前面兩個它依賴的資料計算好，因此我們可以從左至右計算fib陣列，這樣的話我們在計算第n個fib數的時候前面n - 1個fib數已經計算好了，

因此我們的代碼可以像下面這樣：

public static int fibonacci(int n) {
    if (n <= 1)
        return n;
    int[] fib = new int[n + 1];
    // 進行初始化操作
    fib[0] = 0;
    fib[1] = 1;
    // 從前往后遍歷得到 fib 陣列的結果
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

這種方式我們得到的時間和空間復雜度都降為了O(n)，

斐波拉契數列——陣列法優化空間復雜度

根據上面的分析我們可以知道，我們在計算第n個斐波拉契數的時候僅僅依賴它前面的兩個資料，因此我們無需用一個資料將所有的資料都保存下來，我們可以只用兩個變數保存他前面的兩個值即可，然后在進行for回圈的時候不斷進行更新就行了，

public static int fibonacci(int n) {
    if (n <= 1)
        return n;
    // 進行初始化操作
    int a = 0;
    int b = 1;
    int fib = 0;
    // 從前往后遍歷得到 fib 的結果
    for (int i = 2; i <= n; i++) {
        fib = a + b;
        a = b;
        b = fib;
    }
    return fib;
}

這樣我們的時間復雜度為O(n)空間復雜度就降低到了O(1)，

斐波拉契數列——矩陣乘法優化時間復雜度

我們已經知道斐波拉契數列的公式為：

\[fib[i] = fib[i - 1] + fib[i - 2], i \ge 2 \]

\[fib[n + 2] = fib[i + 1] + fib[i] \]

又因為：

\[fib[n + 1] = fib[n + 1] \]

根據上面的公式，我們根據矩陣乘法原理可以得到：

我們將n - 1得到：

我們不停的對上式最右側公式進行展開可以得到

從上式看，我們如果想求fib[n]的值，需要計算矩陣的冪，如果我們直接計算的話，時間復雜度為達到O(n)，但是我們希望能夠將時間復雜度降低到O(log(n))，在正式求解矩陣冪之前，我們先思考一個問題，如何在計算\(a^n\)時將時間復雜度降低到O(log(n))，

快速計算整數冪

首先我們先明確我們的目標：在計算\(a^n\)時將時間復雜度降低到O(log(n))，這個問題我們可以直接使用一個回圈就可以解決，但是時間復雜度為O(n)：

  /**
   * 這個函式的目的是求解 base 的 n 次方
   * @param base
   * @param n
   * @return
   */
    public static int pow(int base, int n) {
        int ans = 1;
        for (int i = 0; i < n; i++)
            ans *= base;
        return ans;
    }

我們知道計算機在進行運算的時候都是采用2進制進行運算，所有的正整數如果是2的整數次冪的話，資料的二進制當中只有一個為為1，其余位置為0，

我們知道一個資料用二進制表示只有某些位置為0，某些位置為1，那么一個整數一定可以用若干個整數相加得到，而且這些整數滿足2的整數次冪，比如下圖中的7 = 1 + 2 + 4：

同樣的我們需要求解的\(2^n\)上的n也是可以通過加法得到，比如說\(2^7 = 2^1 * 2^2 * 2^4 = 2^{(1 + 2 + 4)}\)，因此我們可以使用下面的代碼進行快速冪的求解：

  /**
   * 這個函式的目的是求解 base 的 n 次方
   * @param base
   * @param n
   * @return
   */
  public static int power(int base, int n) {
    if (n == 0) return 1;
    int ans = 1;
    for (int i = 0; i < n; i++) {
      // 這個右移的目的是查看 n 第i個位元位置上是否為 1 如果為 1 就需要進行乘法運算
      // 這就相當于 ans *= base^i
      if (((n >> i) & 1) == 1) {
        ans *= base; // 這就相當于 冪相加 可以仔細分析上面的 2^7 的運算方式
      }
      // base 的變化情況為 base^1, base^2, base^3, base^4, ...
      // 比如說當 base 為 2 時，base 的變化情況為 1, 2, 4, 8, 16, 32, 64, ...
      base *= base;
    }
    return ans;
  }

斐波拉契資料列矩陣乘法的快速冪

首先在我們計算當中需要進行一個2x2的矩陣乘法運算，首先我們先定義一個簡單的2x2矩陣乘法運算，

  /**
   * 這里為了簡單期間，因為我們的矩陣乘法是 2x2 的
   * 所以可以直接做這樣的簡單的乘法
   * @param a
   * @param b
   * @return
   */
  public static int[][] matrixMultiply(int[][] a, int[][] b) {
    int[][] ans = new int[2][2];
    ans[0][0] = b[0][0] * a[0][0] + b[0][1] * a[1][0];
    ans[0][1] = b[0][0] * a[0][1] + b[0][1] * a[1][1];
    ans[1][0] = b[1][0] * a[0][0] + b[1][1] * a[1][0];
    ans[1][1] = b[1][0] * a[0][1] + b[1][1] * a[1][1];
    return ans;
  }

我們現在來看我們使用矩陣快速冪得到斐波拉契數列的結果：

public static int fibonacci(int n) {
    if (n <= 1) return n;
    // 這個函式的作用是得到前面提到的矩陣的 n 次冪的結果
    int[][] mm = fibMatrixPower(n); // 這個函式的具體實作在下面
    // 根據下圖當中的公式容易知道我們最侄訓傳的結果就是 mm[1][0] 因為 fib[1] = 1 fib[0] = 0
    return mm[1][0];
}

public static int[][] fibMatrixPower(int n) {
    // 這個矩陣是根據上圖我們的公式得到的
    int[][] baseMatrix = {{1, 1}, {1, 0}};
    if (n == 1)
        return baseMatrix;
    // 初始化為單位矩陣 如果是整數冪 初始化為 1
    // 這里初始化為單位矩陣的目的是因為單位矩陣和任何矩陣
    // 相乘結果都為原矩陣
    int[][] ans = {{1, 0}, {0, 1}};

    for (int i = 0; i < n; i++) {
        // 這個右移的目的是查看 n 對應的位置上是否為 1 如果為 1 就需要進行矩陣乘法運算
        if (((n >> i) & 1) == 1) {
            // 進行矩陣乘法運算 相當于整數冪的時候數值乘法
            ans = matrixMultiply(ans, baseMatrix);
        }
        // 進行矩陣乘法運算求矩陣頻發 相當于整數冪的時候數值乘法 求數值的平方
        baseMatrix = matrixMultiply(baseMatrix, baseMatrix);
    }
    return ans;
}

以上就是本文關于求解斐波拉契數列的各種方法，完整代碼如下：

public class Fibonacci {

  public static int fibonacci1(int n) {
    if (n <= 1)
      return n;
    return fibonacci1(n - 1) + fibonacci1(n - 2);
  }

  public static int fibonacci2(int n) {
    if (n <= 1)
      return n;
    int[] fib = new int[n + 1];
    // 進行初始化操作
    fib[0] = 0;
    fib[1] = 1;
    // 從前往后遍歷得到 fib 陣列的結果
    for (int i = 2; i <= n; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
  }

  public static int fibonacci3(int n) {
    if (n <= 1)
      return n;
    // 進行初始化操作
    int a = 0;
    int b = 1;
    int fib = 0;
    // 從前往后遍歷得到 fib 的結果
    for (int i = 2; i <= n; i++) {
      fib = a + b;
      a = b;
      b = fib;
    }
    return fib;
  }

  /**
   * 這個函式的目的是求解 base 的 n 次方
   * @param base
   * @param n
   * @return
   */
  public static int power(int base, int n) {
    if (n == 0) return 1;
    int ans = 1;
    for (int i = 0; i < n; i++) {
      // 這個右移的目的是查看 n 對應的位置上是否為 1 如果為 1 就需要進行乘法運算
      // 這就相當于 ans *= base^i
      if (((n >> i) & 1) == 1) {
        ans *= base;
      }
      // base 的變化情況為 base^1 base^2 base^3 ...
      // 比如說當 base 為 2 時，base 的變化情況為 1, 2, 4, 8, 16, 32, 64, ...
      base *= base;
    }
    return ans;
  }

  public static int pow(int base, int n) {
    int ans = 1;
    for (int i = 0; i < n; i++)
      ans *= base;
    return ans;
  }

  /**
   * 這里為了簡單期間，因為我們的矩陣乘法是 2x2 的
   * 所以可以直接做這樣的簡單的乘法
   * @param a
   * @param b
   * @return
   */
  public static int[][] matrixMultiply(int[][] a, int[][] b) {
    int[][] ans = new int[2][2];
    ans[0][0] = b[0][0] * a[0][0] + b[0][1] * a[1][0];
    ans[0][1] = b[0][0] * a[0][1] + b[0][1] * a[1][1];
    ans[1][0] = b[1][0] * a[0][0] + b[1][1] * a[1][0];
    ans[1][1] = b[1][0] * a[0][1] + b[1][1] * a[1][1];
    return ans;
  }

  public static int[][] fibMatrixPower(int n) {
    int[][] baseMatrix = {{1, 1}, {1, 0}};
    if (n == 1)
      return baseMatrix;
    // 初始化為單位矩陣 如果是整數冪 初始化為 1
    int[][] ans = {{1, 0}, {0, 1}};

    for (int i = 0; i < n; i++) {
      // 這個右移的目的是查看 n 對應的位置上是否為 1 如果為 1 就需要進行矩陣乘法運算
      if (((n >> i) & 1) == 1) {
        ans = matrixMultiply(ans, baseMatrix);
      }

      baseMatrix = matrixMultiply(baseMatrix, baseMatrix);
    }

    return ans;
  }

  public static int fibonacci(int n) {
    if (n <= 1) return n;
    int[][] mm = fibMatrixPower(n);
    return mm[1][0];
  }

  public static void main(String[] args) {
    System.out.println(fibonacci1(1));
//    System.out.println(power(2, 8));
//    System.out.println(power(2, 8));
    System.out.println(fibonacci(1));
  }
}

我們從斐波拉契數列得到了什么

我們現在來重新捋一下我們在上面學習斐波拉契數列的思路：

首先我們用于解決斐波拉契數列的方法是遞回法但是這個方法有一個很大的問題，就是計算某個斐波拉契數的時候它依賴于它前面的斐波拉契數（這個程序相當于將一個大問題劃分成若干個小問題），這個依賴會導致我們進行很多重復的運算，為了解決這個問題我們用到了陣列法，這其實就是一個用空間換時間的方法，用陣列將前面計算你的結果存盤下來，避免重復計算，

通過分析我們公式，我們發現我們的資料依賴關系，我們在計算某個斐波拉契數的時候只需要依賴它前面的兩個斐波拉契數，因此我們不用存盤我們計算的每一個斐波拉契數，只需要保存兩個值即可，這就是我們優化陣列法的原理，

最后我們通過快速矩陣冪的方法將我們的時間復雜度從O(n)降低到了O(long(n))，這個方法其實帶有一定的技巧性，在大多數動態規劃的演算法當中我們用不到它，也就是說它的普適性并不強，

從上面的分析我們可以總結我們在使用動態規劃時的大致思路：

將大問題劃分成小問題，小問題繼續劃分......，學術一點的話說就是重疊子問題，
是否存在重復計算，如果存在使用空間換時間的方法進行優化，這是動態規劃一個非常重要的點，
是否能夠對陣列的空間復雜度進行優化，

01背包問題

背包問題：有 \(N\)件物品和一個能夠承受重量為 \(V\) 的背包，每件物品只能使用一次，第 \(i\) 件物品的價值是 \(v_i\)，重量是 \(w_i\)，求解將哪些物品裝入背包，可使這些物品的總體積不超過背包能夠承受的重量，且總價值最大，

比如下面的4個物品，背包能夠承受的最大重量為5，我們應該如何選擇，使得我們獲得的總價值最大：

物品	重量	價值
A	1	2
B	2	4
C	3	4
D	4	5

這個問題還是比較簡單，我們直接看就知道選擇物品B和物品C得到的價值最大，那么我們如何設計一個演算法去實作這個問題呢？首先對于每一個物品都有兩種情況，選擇和不選擇，我們需要選擇兩種情況當中能夠獲取最大價值的那種情況，

選擇或者不選擇

在動態規劃當中我們通常通過陣列進行求解，在01背包問題當中，我們設定一個陣列dp[i][j]，表示當我們只使用前i個物品（物品編號從0開始，第一個物品的下標為0）且當前剩余能夠承受的重量為j時，能夠獲取的最大的價值，那么我們要求解的值為dp[N - 1][V]，物品下標從0開始，

比如說：dp[2][3]表示在本題當中的四個物品A,B,C,D當中只選擇前面兩個物品A,B，且背包還能夠承受3de 重量，

根據上面的分析我們可以得到下面一個動態規劃公式：

dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])，其中w和v分別表示第i個物品的重量和價值，

你真的理解了背包問題for回圈的順序嗎

我們已經得到了我們的動態轉移公式dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])，我們現在了來好好分析這個公式：

我們可以很清楚的看到要想求解dp[i][j]的值，我們首先需要知道dp[i - 1][j - w]和dp[i - 1][j]的值，他們之間的依賴關系可以用下圖來表示，

我們在求解dp[i][j]的值的時候，首先的需要求出它依賴的資料，當我們在求解第動態規劃陣列dp的第i行時，我們首先需要求出第i - 1行的值，但是我們在求第0行的時候并沒有-1行，因此我們首先需要進行初始化，dp[i][j]的含義是只使用前i個物品且承受重量只有j時，我們能過獲取的最大的價值！！！

那么初始化dp[0][j]的含義就是當我們只有第1個物品可選擇而且背包能夠承受的重量為j時能夠獲取的最大的價值，那么我們很容易進行初始化（當j大于等于物品的重量的時候可以獲取第一個物品的價值，否則獲取價值為0，因為只有一個物品，但是背包承受不了它的重量）：

Java代碼實作動態規劃：

import java.util.Scanner;

public class Main {


  public static int backpack(int[] w, int[] v, int V) {
    int N = w.length;
    int[][] dp = new int[N][V + 1];

    // 我們一共有 N 個物品，背包能夠承受的重量為 V
    // dp陣列就是我們上面提到的動態規劃的陣列
    // w[i] 就是第 i 個物品的重量
    // v[i] 就是第 i 個物品的價值
    // 進行陣列的初始化
    for (int i = w[0]; i < V; ++i) {
      dp[0][i] = v[0];
    }
    for (int i = 1; i < N; ++i) {
      for (int j = 0; j <= V; ++j) {
        if (j >= w[i]) // 只有能夠承受物品的重量才能進行選擇
          dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        else
          dp[i][j] = dp[i - 1][j];
      }
    }
    // 回傳能夠獲得的最大的價值
    // 這個式子表明前 N - 1個可選擇且我們的背包承受重量為 V 時最大收益
    return dp[N - 1][V];
  }


  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int V = scanner.nextInt();
    int[] w = new int[N];
    int[] v = new int[N];
    for (int i = 0; i < N; i++) {
      w[i] = scanner.nextInt();
      v[i] = scanner.nextInt();
    }
    System.out.println(backpack(w, v, V));
  }
}

C++代碼實作動態規劃

#include <iostream>
using namespace std;

#define LENTGH 1005
int N, V;
int v[LENTGH];
int w[LENTGH];
int dp[LENTGH][LENTGH];

int backpack() {
	// 我們一共有 N 個物品，背包能夠承受的重量為 V
	// dp陣列就是我們上面提到的動態規劃的陣列
	// w[i] 就是第 i 個物品的重量
	// v[i] 就是第 i 個物品的價值
	// 進行陣列的初始化
	for (int i = w[0]; i < V; ++i) {
		dp[0][i] = v[0];
	}
	for (int i = 1; i < N; ++i) {
		for (int j = 0; j <= V; ++j) {
			if (j >= w[i]) // 只有能夠承受物品的重量才能進行選擇
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
			else
				dp[i][j] = dp[i - 1][j];
		}
	}
	// 回傳能夠獲得的最大的價值
	// 這個式子表明前 N - 1個可選擇且我們的背包承受重量為 V 時最大收益
	return dp[N - 1][V];
}

int main() {
	cin >> N >> V;
	for (int i = 0; i < N; ++i) {
		cin >> w[i] >> v[i];
	}
	cout << backpack();
	return 0;
}

我們在上述兩份代碼當中的for回圈順序是遍歷所有的物品，然后背包容量從0變化到V，那么我們背包容量變化能不能從V變化到0呢？答案是可以的：

從上圖看我們在計算第i的資料的時候我們只依賴第i - 1行，我們在第i行從后往前遍歷并不會破壞動態轉移公式的要求，

下面的代碼同樣可以是正確的：

public static int backpack(int[] w, int[] v, int V) {
    int N = w.length;
    int[][] dp = new int[N][V + 1];

    // 我們一共有 N 個物品，背包能夠承受的重量為 V
    // dp陣列就是我們上面提到的動態規劃的陣列
    // w[i] 就是第 i 個物品的重量
    // v[i] 就是第 i 個物品的價值
    // 進行陣列的初始化
    for (int i = w[0]; i < V; ++i) {
        dp[0][i] = v[0];
    }
    for (int i = 1; i < N; ++i) {
        for (int j = V; j >= 0; --j) {
            if (j >= w[i]) // 只有能夠承受物品的重量才能進行選擇
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    // 回傳能夠獲得的最大的價值
    // 這個式子表明前 N - 1個
    return dp[N - 1][V];
}

背包問題的空間優化——滾動陣列

我們在解決背包問的時候我們是開辟了一個二維陣列dp，那么我們能不能想斐波拉契數列那樣降低演算法的空間復雜度呢？我們已經很清楚了我們在計算dp資料的時候進行計算的時候只使用了兩行資料，那么我們只需要申請兩行的空間即可，不需要申請那么大的陣列空間，計算的時候反復在兩行資料當中交替計算既可，比如說我們已經計算好第一行的資料了（初始化），那么我們可以根據第一行得到的結果得到第二行，然后根據第二行，將計算的結結果重新存盤到第一行，如此交替反復，像這種方法叫做滾動陣列，

  public static int backpack(int[] w, int[] v, int V) {
    int N = w.length;
    int[][] dp = new int[2][V + 1];

    // 我們一共有 N 個物品，背包能夠承受的重量為 V
    // dp陣列就是我們上面提到的動態規劃的陣列
    // w[i] 就是第 i 個物品的重量
    // v[i] 就是第 i 個物品的價值
    // 進行陣列的初始化
    for (int i = w[0]; i < V; ++i) {
      dp[0][i] = v[0];
    }
    for (int i = 1; i < N; ++i) {
      for (int j = V; j >= 0; --j) {
        if (j >= w[i]) // 只有能夠承受物品的重量才能進行選擇
          dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j],
              dp[(i - 1) % 2][j - w[i]] + v[i]);
        else
          dp[i % 2][j] = dp[(i - 1) % 2][j];
      }
    }
    // 回傳能夠獲得的最大的價值
    // 這個式子表明前 N - 1個
    return dp[(N - 1) % 2][V];
  }

背包空間再優化——單行陣列和它的遍歷順序問題

我們還能繼續壓縮空間嗎??？我們在進行空間問題的優化的時候只要不破壞動態轉移公式，只需要我們進行的優化能夠滿足dp[i][j]的計算在它所依賴的資料之后計算即可，

public static int backpack(int[] w, int[] v, int V) {
    int N = w.length;
    int[] dp = new int[V + 1];
    // 我們一共有 N 個物品，背包能夠承受的重量為 V
    // dp陣列就是我們上面提到的動態規劃的陣列
    // w[i] 就是第 i 個物品的重量
    // v[i] 就是第 i 個物品的價值
    // 進行陣列的初始化
    for (int i = w[0]; i < V; ++i) {
        dp[i] = v[0];
    }
    for (int i = 1; i < N; ++i) {
        for (int j = V; j >= w[i]; --j) {
            dp[j] = Math.max(dp[j - w[i]] + v[i], dp[j]);
        }
    }
    return dp[V];
}

我們現在來好好分析一下上面的代碼：

根據動態轉移公式dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])我們知道，第i行的資料只依賴第i - 1行的前j個資料，跟第j個資料之后的資料沒有關系，因此我們在使用一維陣列的時候可以從后往前計算（且只能從后往前計算，如果從前往后計算會破話動態轉移公式，因為第j個資料跟他前面的資料有依賴關系，跟他后面的資料沒有依賴關系）就能夠滿足我們的動態轉移公式，

如果我們從在使用單行陣列的時候從前往后計算，那么會使得一維資料前面部分資料的狀態從i - 1行的狀態變成第i行的狀態，像下面這樣，

但是一維陣列當中后部分的資料還是i - 1行的狀態，當我們去更新他們的時候他們依賴前面部分資料的i - 1行的狀態，但是他們已經更新到第i的狀態了，因此破壞了動態規劃的轉移方程，但是如果我們從后往前進行遍歷那么前面的狀態始終是第i - 1行的狀態，因此沒有破壞動態規劃的轉移方程，因此我們需要從后往前遍歷，

動態規劃總結

動態規劃的套路

通過仔細分析上面兩個演算法題，我們可以得到下面的一些心得：

動態規劃有著時間換空間的特點，這樣可以降低演算法的時間復雜度，
動態規劃一般都有重疊子問題，我們需要分析重疊子問題，得到動態轉移方程，比如在斐波拉契數列當中的轉移方程為f(i) = f(i - 1) + f(2)，背包問題的動態轉移方程為dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])，
得到轉移方程之后，我們需要進行陣列的初始化，比如在斐波拉契數列當中我們需要初始化下標為0和1的資料，在背包問題當中我們要初始化第一行的資料，
根據上面得到的資訊進行for回圈操作，運算得到最終的結果，
分析是否能夠優化空間復雜度，

動態規劃為什么叫動態規劃

學習完以上兩個問題之后我們可以通過動態規劃的特點去找到這個答案，首先我們需要明白什么是規劃所謂的規劃 就是尋找最優值的程序，比如說我們在旅行的時候做規劃就是為了又更好旅行體驗，而我們在做演算法題的時候需要找到最好的結果，比如在背包問題當中我們要找到價值最大的一種選擇，這也是一種規劃，那為什么是動態的呢？所謂動態就是我們在尋找最優值的程序當中，選擇是變化的，比如說對于背包問題的公式dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])我們在計算出結果之前并不知道那種選擇好，因為我們要選擇兩者中間值較大的哪個選擇，這就是動態選擇的程序！！！

以上就是本篇文章的所有內容了，希望大家有所識訓，我是LeHung，我們下期再見！！！

更多內容在專案https://github.com/Chang-LeHung/CSCore!!!

關注公眾號：一無是處的研究僧，了解更多計算機知識，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498633.html

標籤：其他

上一篇：猴子吃桃（遞回）

下一篇：【學習筆記】網路流