庖丁解牛斐波拉契數列和揹包問題——詳細解析兩個問題優化過程，帶你從最基本的問題看懂動態規劃！！！
庖丁解牛斐波拉契數列和揹包問題——詳細解析兩個問題優化過程，帶你從最基本的問題看懂動態規劃！！！
（如果公式不能很好的渲染，請檢視這篇同樣內容而且能夠渲染公式的文章）
動態規劃作為一種非常經典的一類演演算法，不僅在解決實際問題當中有很多實際的應用，同時通常也是面試的一個重點。本篇文章一步步剖析動態規劃的基本原理，通過斐波拉契數列問題（優化時間複雜度從$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：
同樣的我們需要求解的$2n$上的`n`也是可以通過加法得到，比如說$27 = 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];
}
揹包空間再優化——單行陣列和它的遍歷順序問題
我們還能繼續壓縮空間嗎