1. 介紹

動態規劃典型的被用于優化遞歸算法，因為它們傾向于以指數的方式進行擴展。動態規劃主要思想是將復雜問題(帶有許多遞歸調用)分解為更小的子問題，然后將它們保存到內存中，這樣我們就不必在每次使用它們時重新計算它們。

要理解動態規劃的概念，我們需要熟悉一些主題：

什么是動態規劃？

貪心算法

簡化的背包問題

傳統的背包問題

Levenshtein Distance

LCS-最長的共同子序列

利用動態規劃的其他問題

結論

本文所有代碼均為java代碼實現。

2. 什么是動態規劃？

動態規劃是一種編程原理，可以通過將非常復雜的問題劃分為更小的子問題來解決。這個原則與遞歸很類似，但是與遞歸有一個關鍵點的不同，就是每個不同的子問題只能被解決一次。

為了理解動態規劃，我們首先需要理解遞歸關系的問題。每個單獨的復雜問題可以被劃分為很小的子問題，這表示我們可以在這些問題之間構造一個遞歸關系。

讓我們來看一個我們所熟悉的例子：斐波拉契數列，斐波拉契數列的定義具有以下的遞歸關系：

注意：遞歸關系是遞歸地定義下一項是先前項的函數的序列的等式。Fibonacci序列就是一個很好的例子。

所以，如果我們想要找到斐波拉契數列序列中的第n個數，我們必須知道序列中第n個前面的兩個數字。

但是，每次我們想要計算Fibonacci序列的不同元素時，我們在遞歸調用中都有一些重復調用，如下圖所示，我們計算Fibonacci(5)：

例如：如果我們想計算F(5),明顯的我們需要計算F(3)和F(4)作為計算F(5)的先決條件。然而，為了計算F(4)，我們需要計算F(3)和F(2)，因此我們又需要計算F(2)和F(1)來得到F(3)，其他的求解諸如此類。

這樣的話就會導致很多重復的計算，這些重復計算本質上是冗余的，并且明顯的減慢了算法的效率。為了解決這種問題，我們介紹動態規劃。

在這種方法中，我們對解決方案進行建模，就像我們要遞歸地解決它一樣，但我們從頭開始解決它，記憶到達頂部采取的子問題(子步驟)的解決方案。

因此，對于Fibonacci序列，我們首先求解并記憶F(1)和F(2)，然后使用兩個記憶步驟計算F(3)，依此類推。這意味著序列中每個單獨元素的計算都是O(1)，因為我們已經知道前兩個元素。

當使用動態規劃解決問題的時候，我們一般會采用下面三個步驟：

確定適用于所述問題的遞歸關系

初始化內存、數組、矩陣的初始值

確保當我們進行遞歸調用(可以訪問子問題的答案)的時候它總是被提前解決。

遵循這些規則，讓我們來看一下使用動態規劃的算法的例子：

3. 貪心算法

下面來以這個為例子：

Given a rod of length n and an array that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

3.1. 對于沒有經驗的開發者可能會采取下面這種做法

這個問題實際上是為動態規劃量身定做的，但是因為這是我們的第一個真實例子，讓我們看看運行這些代碼會遇到多少問題：

public class naiveSolution { static int getValue(int[] values, int length) { if (length <= 0) return 0; int tmpMax = -1; for (int i = 0; i < length; i++) { tmpMax = Math.max(tmpMax, values[i] + getValue(values, length - i - 1)); } return tmpMax; } public static void main(String[] args) { int[] values = new int[]{3, 7, 1, 3, 9}; int rodLength = values.length; System.out.println("Max rod value: " + getValue(values, rodLength)); }}

輸出結果：

Max rod value: 17

該解決方案雖然正確，但效率非常低，遞歸調用的結果沒有保存，所以每次有重疊解決方案時，糟糕的代碼不得不去解決相同的子問題。

3.2.動態方法

利用上面相同的基本原理，添加記憶化并排除遞歸調用，我們得到以下實現:

public class dpSolution { static int getValue(int[] values, int rodLength) { int[] subSolutions = new int[rodLength + 1]; for (int i = 1; i <= rodLength; i++) { int tmpMax = -1; for (int j = 0; j < i; j++) tmpMax = Math.max(tmpMax, values[j] + subSolutions[i - j - 1]); subSolutions[i] = tmpMax; } return subSolutions[rodLength]; } public static void main(String[] args) { int[] values = new int[]{3, 7, 1, 3, 9}; int rodLength = values.length; System.out.println("Max rod value: " + getValue(values, rodLength)); }}

輸出結果：

Max rod value: 17

正如我們所看到的的，輸出結果是一樣的，所不同的是時間和空間復雜度。

通過從頭開始解決子問題，我們消除了遞歸調用的需要，利用已解決給定問題的所有先前子問題的事實。

性能的提升

為了給出動態方法效率更高的觀點的證據，讓我們嘗試使用30個值來運行該算法。 一種算法需要大約5.2秒來執行，而動態解決方法需要大約0.000095秒來執行。

4. 簡化的背包問題

簡化的背包問題是一個優化問題，沒有一個解決方案。這個問題的問題是 - “解決方案是否存在？”：

Given a set of items, each with a weight w1, w2... determine the number of each item to put in a knapsack so that the total weight is less than or equal to a given limit K.

給定一組物品，每個物品的重量為w1，w2 …確定放入背包中的每個物品的數量，以使總重量小于或等于給定的極限K

首先讓我們把元素的所有權重存儲在W數組中。接下來，假設有n個項目，我們將使用從1到n的數字枚舉它們，因此第i個項目的權重為W [i]。我們將形成(n + 1)x(K + 1)維的矩陣M。M [x] [y]對應于背包問題的解決方案，但僅包括起始數組的前x個項，并且最大容量為y

例如

假設我們有3個元素，權重分別是w1=2kg,w2=3kg,w3=4kg。利用上面的方法，我們可以說M [1] [2]是一個有效的解決方案。

這意味著我們正在嘗試用重量陣列中的第一個項目(w1)填充容量為2kg的背包。

在M [3] [5]中，我們嘗試使用重量陣列的前3項(w1，w2，w3)填充容量為5kg的背包。

這不是一個有效的解決方案，因為我們過度擬合它。

4.1. 矩陣初始化

當初始化矩陣的時候有兩點需要注意：

Does a solution exist for the given subproblem (M[x][y].exists) AND does the given solution include the latest item added to the array (M[x][y].includes).

給定子問題是否存在解(M [x] [y] .exists)并且給定解包括添加到數組的最新項(M [x] [y] .includes)。

因此，初始化矩陣是相當容易的，M[0][k].exists總是false，如果k>0，因為我們沒有把任何物品放在帶有k容量的背包里。

另一方面，M[0][0].exists = true,當k=0的時候，背包應該是空的，因此我們在里面沒有放任何東西，這個是一個有效的解決方案。

此外，我們可以說M[k][0].exists = true，但是對于每個k來說 M[k][0].includes = false。

注意：僅僅因為對于給定的M [x] [y]存在解決方案，它并不一定意味著該特定組合是解決方案。

在M [10] [0]的情況下，存在一種解決方案 - 不包括10個元素中的任何一個。

這就是M [10] [0] .exists = true但M [10] [0] .includes = false的原因。

4.2.算法原則

接下來，讓我們使用以下偽代碼構造M [i] [k]的遞歸關系：

if (M[i-1][k].exists == True): M[i][k].exists = True M[i][k].includes = Falseelif (k-W[i]>=0): if(M[i-1][k-W[i]].exists == true): M[i][k].exists = True M[i][k].includes = Trueelse: M[i][k].exists = False

因此，解決方案的要點是將子問題分為兩種情況:

對于容量k,當存在第一個i-1元素的解決方案

對于容量k-W [i],當第一個i-1元素存在解決方案

第一種情況是不言自明的，我們已經有了問題的解決方案。

第二種情況是指了解第一個i-1元素的解決方案，但是容量只有一個第i個元素不滿，這意味著我們可以添加一個第i個元素，并且我們有一個新的解決方案！

4.3. 實現

下面這何種實現方式，使得事情變得更加容易，我們創建了一個類Element來存儲元素：

public class Element { private boolean exists; private boolean includes; public Element(boolean exists, boolean includes) { this.exists = exists; this.includes = includes; } public Element(boolean exists) { this.exists = exists; this.includes = false; } public boolean isExists() { return exists; } public void setExists(boolean exists) { this.exists = exists; } public boolean isIncludes() { return includes; } public void setIncludes(boolean includes) { this.includes = includes; }}

接著，我們可以深入了解主要的類：

public class Knapsack { public static void main(String[] args) { Scanner scanner = new Scanner (System.in); System.out.println("Insert knapsack capacity:"); int k = scanner.nextInt(); System.out.println("Insert number of items:"); int n = scanner.nextInt(); System.out.println("Insert weights: "); int[] weights = new int[n + 1]; for (int i = 1; i <= n; i++) { weights[i] = scanner.nextInt(); } Element[][] elementMatrix = new Element[n + 1][k + 1]; elementMatrix[0][0] = new Element(true); for (int i = 1; i <= k; i++) { elementMatrix[0][i] = new Element(false); } for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { elementMatrix[i][j] = new Element(false); if (elementMatrix[i - 1][j].isExists()) { elementMatrix[i][j].setExists(true); elementMatrix[i][j].setIncludes(false); } else if (j >= weights[i]) { if (elementMatrix[i - 1][j - weights[i]].isExists()) { elementMatrix[i][j].setExists(true); elementMatrix[i][j].setIncludes(true); } } } } System.out.println(elementMatrix[n][k].isExists()); }}

唯一剩下的就是解決方案的重建，在上面的類中，我們知道解決方案是存在的，但是我們不知道它是什么。

為了重建，我們使用下面的代碼：

List solution = new ArrayList<>(n);if (elementMatrix[n][k].isExists()) { int i = n; int j = k; while (j > 0 && i > 0) { if (elementMatrix[i][j].isIncludes()) { solution.add(i); j = j - weights[i]; } i = i - 1; }}System.out.println("The elements with the following indexes are in the solution:" + (solution.toString()));

輸出：

Insert knapsack capacity: 12 Insert number of items: 5 Insert weights: 9 7 4 10 3 true The elements with the following indexes are in the solution: [5, 1]

背包問題的一個簡單變化是在沒有價值優化的情況下填充背包，但現在每個單獨項目的數量無限。

通過對現有代碼進行簡單調整，可以解決這種變化：

// Old code for simplified knapsack problemelse if (j >= weights[i]) { if (elementMatrix[i - 1][j - weights[i]].isExists()) { elementMatrix[i][j].setExists(true); elementMatrix[i][j].setIncludes(true); }}// New code, note that we're searching for a solution in the same// row (i-th row), which means we're looking for a solution that// already has some number of i-th elements (including 0) in it's solutionelse if (j >= weights[i]) { if (elementMatrix[i][j - weights[i]].isExists()) { elementMatrix[i][j].setExists(true); elementMatrix[i][j].setIncludes(true); }}

5. 傳統的背包問題

利用以前的兩種變體，現在讓我們來看看傳統的背包問題，看看它與簡化版本的不同之處：

Given a set of items, each with a weight w1, w2... and a value v1, v2... determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit k and the total value is as large as possible.

在簡化版中，每個解決方案都同樣出色。但是，現在我們有一個找到最佳解決方案的標準(也就是可能的最大值)。請記住，這次我們每個項目都有無限數量，因此項目可以在解決方案中多次出現。

在實現中，我們將使用舊的類Element，其中添加了私有字段value，用于存儲給定子問題的最大可能值:

public class Element { private boolean exists; private boolean includes; private int value; // appropriate constructors, getters and setters}

實現非常相似，唯一的區別是現在我們必須根據結果值選擇最佳解決方案：

public static void main(String[] args) { // Same code as before with the addition of the values[] array System.out.println("Insert values: "); int[] values = new int[n + 1]; for (int i=1; i <= n; i++) { values[i] = scanner.nextInt(); } Element[][] elementMatrix = new Element[n + 1][k + 1]; // A matrix that indicates how many newest objects are used // in the optimal solution. // Example: contains[5][10] indicates how many objects with // the weight of W[5] are contained in the optimal solution // for a knapsack of capacity K=10 int[][] contains = new int[n + 1][k + 1]; elementMatrix[0][0] = new Element(0); for (int i = 1; i <= n; i++) { elementMatrix[i][0] = new Element(0); contains[i][0] = 0; } for (int i = 1; i <= k; i++) { elementMatrix[0][i] = new Element(0); contains[0][i] = 0; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { elementMatrix[i][j] = new Element(elementMatrix[i - 1][j].getValue()); contains[i][j] = 0; elementMatrix[i][j].setIncludes(false); elementMatrix[i][j].setValue(M[i - 1][j].getValue()); if (j >= weights[i]) { if ((elementMatrix[i][j - weights[i]].getValue() > 0 || j == weights[i])) { if (elementMatrix[i][j - weights[i]].getValue() + values[i] > M[i][j].getValue()) { elementMatrix[i][j].setIncludes(true); elementMatrix[i][j].setValue(M[i][j - weights[i]].getValue() + values[i]); contains[i][j] = contains[i][j - weights[i]] + 1; } } } System.out.print(elementMatrix[i][j].getValue() + "/" + contains[i][j] + " "); } System.out.println(); } System.out.println("Value: " + elementMatrix[n][k].getValue());}

輸出：

Insert knapsack capacity: 12 Insert number of items: 5 Insert weights: 9 7 4 10 3 Insert values: 1 2 3 4 5 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 1/1 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 2/1 0/0 1/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 3/1 0/0 0/0 2/0 6/2 1/0 0/0 5/1 9/3 0/0 0/0 0/0 0/0 3/0 0/0 0/0 2/0 6/0 1/0 4/1 5/0 9/0 0/0 0/0 0/0 5/1 3/0 0/0 10/2 8/1 6/0 15/3 13/2 11/1 20/4 Value: 20

6. Levenshtein Distance

另一個使用動態規劃的非常好的例子是Edit Distance或Levenshtein Distance。

Levenshtein Distance就是兩個字符串A,B,我們需要使用原子操作將A轉換為B：

字符串刪除

字符串插入

字符替換(從技術上講，它不止一個操作，但為了簡單起見，我們稱之為原子操作)

這個問題是通過有條理地解決起始字符串的子串的問題來處理的，逐漸增加子字符串的大小，直到它們等于起始字符串。

我們用于此問題的遞歸關系如下：

如果a == b則c(a，b)為0，如果a = = b則c(a，b)為1。

實現：

public class editDistance { public static void main(String[] args) { String s1, s2; Scanner scanner = new Scanner(System.in); System.out.println("Insert first string:"); s1 = scanner.next(); System.out.println("Insert second string:"); s2 = scanner.next(); int n, m; n = s1.length(); m = s2.length(); // Matrix of substring edit distances // example: distance[a][b] is the edit distance // of the first a letters of s1 and b letters of s2 int[][] distance = new int[n + 1][m + 1]; // Matrix initialization: // If we want to turn any string into an empty string // the fastest way no doubt is to just delete // every letter individually. // The same principle applies if we have to turn an empty string // into a non empty string, we just add appropriate letters // until the strings are equal. for (int i = 0; i <= n; i++) { distance[i][0] = i; } for (int j = 0; j <= n; j++) { distance[0][j] = j; } // Variables for storing potential values of current edit distance int e1, e2, e3, min; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { e1 = distance[i - 1][j] + 1; e2 = distance[i][j - 1] + 1; if (s1.charAt(i - 1) == s2.charAt(j - 1)) { e3 = distance[i - 1][j - 1]; } else { e3 = distance[i - 1][j - 1] + 1; } min = Math.min(e1, e2); min = Math.min(min, e3); distance[i][j] = min; } } System.out.println("Edit distance of s1 and s2 is: " + distance[n][m]); }}

輸出：

Insert first string: man Insert second string: machine Edit distance of s1 and s2 is: 3

如果你想了解更多關于Levenshtein Distance的解決方案，我們在另外的一篇文章中用python實現了 Levenshtein Distance and Text Similarity in Python，

使用這個邏輯，我們可以將許多字符串比較算法歸結為簡單的遞歸關系，它使用Levenshtein Distance的基本公式

7. 最長共同子序列(LCS)

這個問題描述如下：

Given two sequences, find the length of the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

給定兩個序列，找到兩個序列中存在的最長子序列的長度。子序列是以相同的相對順序出現的序列，但不一定是連續的.

闡明：

如果我們有兩個字符串s1="MICE"和s2="MINCE

總結

以上是生活随笔為你收集整理的矩阵连乘 动态规划_Java动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。