欧美vvv,亚洲第一成人在线,亚洲成人欧美日韩在线观看,日本猛少妇猛色XXXXX猛叫

點(diǎn)擊藍(lán)色“程序猿DD”關(guān)注我

回復(fù)“資源”獲取獨(dú)家整理的學(xué)習(xí)資料！

1. 介紹

動態(tài)規(guī)劃典型的被用于優(yōu)化遞歸算法，因?yàn)樗鼈儍A向于以指數(shù)的方式進(jìn)行擴(kuò)展。動態(tài)規(guī)劃主要思想是將復(fù)雜問題（帶有許多遞歸調(diào)用）分解為更小的子問題，然后將它們保存到內(nèi)存中，這樣我們就不必在每次使用它們時重新計算它們。

要理解動態(tài)規(guī)劃的概念，我們需要熟悉一些主題：

什么是動態(tài)規(guī)劃？

貪心算法

簡化的背包問題

傳統(tǒng)的背包問題

LCS-最長的共同子序列

利用動態(tài)規(guī)劃的其他問題

結(jié)論

本文所有代碼均為java代碼實(shí)現(xiàn)。

2. 什么是動態(tài)規(guī)劃？

動態(tài)規(guī)劃是一種編程原理，可以通過將非常復(fù)雜的問題劃分為更小的子問題來解決。這個原則與遞歸很類似，但是與遞歸有一個關(guān)鍵點(diǎn)的不同貪心算法 背包問題 c語言，就是每個不同的子問題只能被解決一次。

為了理解動態(tài)規(guī)劃，我們首先需要理解遞歸關(guān)系的問題。每個單獨(dú)的復(fù)雜問題可以被劃分為很小的子問題，這表示我們可以在這些問題之間構(gòu)造一個遞歸關(guān)系。讓我們來看一個我們所熟悉的例子：斐波拉契數(shù)列，斐波拉契數(shù)列的定義具有以下的遞歸關(guān)系：

注意：遞歸關(guān)系是遞歸地定義下一項(xiàng)是先前項(xiàng)的函數(shù)的序列的等式。序列就是一個很好的例子。

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

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

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

這樣的話就會導(dǎo)致很多重復(fù)的計算，這些重復(fù)計算本質(zhì)上是冗余的，并且明顯的減慢了算法的效率。為了解決這種問題，我們介紹動態(tài)規(guī)劃。

在這種方法中，我們對解決方案進(jìn)行建模，就像我們要遞歸地解決它一樣，但我們從頭開始解決它，記憶到達(dá)頂部采取的子問題（子步驟）的解決方案。因此，對于序列，我們首先求解并記憶F（1）和F（2），然后使用兩個記憶步驟計算F（3），依此類推。這意味著序列中每個單獨(dú)元素的計算都是O（1），因?yàn)槲覀円呀?jīng)知道前兩個元素。

當(dāng)使用動態(tài)規(guī)劃解決問題的時候，我們一般會采用下面三個步驟：

確定適用于所述問題的遞歸關(guān)系

初始化內(nèi)存、數(shù)組、矩陣的初始值

確保當(dāng)我們進(jìn)行遞歸調(diào)用（可以訪問子問題的答案）的時候它總是被提前解決。

遵循這些規(guī)則，讓我們來看一下使用動態(tài)規(guī)劃的算法的例子：

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. 對于沒有經(jīng)驗(yàn)的開發(fā)者可能會采取下面這種做法

這個問題實(shí)際上是為動態(tài)規(guī)劃量身定做的，但是因?yàn)檫@是我們的第一個真實(shí)例子，讓我們看看運(yùn)行這些代碼會遇到多少問題：

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));    }}

輸出結(jié)果：

Max rod value: 17

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

3.2.動態(tài)方法

利用上面相同的基本原理，添加記憶化并排除遞歸調(diào)用，我們得到以下實(shí)現(xiàn):

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));    }}

輸出結(jié)果：

Max rod value: 17

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

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

性能的提升

為了給出動態(tài)方法效率更高的觀點(diǎn)的證據(jù)，讓我們嘗試使用30個值來運(yùn)行該算法。一種算法需要大約5.2秒來執(zhí)行，而動態(tài)解決方法需要大約0.秒來執(zhí)行。

4. 簡化的背包問題

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

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

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

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

例如

假設(shè)我們有3個元素，權(quán)重分別是w1=2kg,w2=3kg,w3=4kg。利用上面的方法，我們可以說M [1] [2]是一個有效的解決方案。這意味著我們正在嘗試用重量陣列中的第一個項(xiàng)目（w1）填充容量為2kg的背包。

在M [3] [5]中，我們嘗試使用重量陣列的前3項(xiàng)（w1，w2，w3）填充容量為5kg的背包。這不是一個有效的解決方案，因?yàn)槲覀冞^度擬合它。

4.1. 矩陣初始化

當(dāng)初始化矩陣的時候有兩點(diǎn)需要注意：

Does a exist for the given (M[x][y].) AND does the given the item added to the array (M[x][y].).

給定子問題是否存在解（M [x] [y] .）并且給定解包括添加到數(shù)組的最新項(xiàng)（M [x] [y] .）。

因此，初始化矩陣是相當(dāng)容易的，M[0][k].總是false，如果k>0，因?yàn)槲覀儧]有把任何物品放在帶有k容量的背包里。

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

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

注意：僅僅因?yàn)閷τ诮o定的M [x] [y]存在解決方案，它并不一定意味著該特定組合是解決方案。在M [10] [0]的情況下，存在一種解決方案 - 不包括10個元素中的任何一個。這就是M [10] [0] . = true但M [10] [0] . = false的原因。

4.2.算法原則

接下來，讓我們使用以下偽代碼構(gòu)造M [i] [k]的遞歸關(guān)系：

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

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

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

對于容量k-W [i],當(dāng)?shù)谝粋€i-1元素存在解決方案

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

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

4.3. 實(shí)現(xiàn)

下面這何種實(shí)現(xiàn)方式，使得事情變得更加容易，我們創(chuàng)建了一個類來存儲元素：

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:\n" + (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]

背包問題的一個簡單變化是在沒有價值優(yōu)化的情況下填充背包，但現(xiàn)在每個單獨(dú)項(xiàng)目的數(shù)量無限。

通過對現(xiàn)有代碼進(jìn)行簡單調(diào)整，可以解決這種變化：

// 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. 傳統(tǒng)的背包問題

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

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.

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

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

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

實(shí)現(xiàn)非常相似，唯一的區(qū)別是現(xiàn)在我們必須根據(jù)結(jié)果值選擇最佳解決方案：

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.

另一個使用動態(tài)規(guī)劃的非常好的例子是Edit 或 。

就是兩個字符串A,B,我們需要使用原子操作將A轉(zhuǎn)換為B：

字符串刪除

字符串插入

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

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

我們用于此問題的遞歸關(guān)系如下：

如果a == b則c（a，b）為0，如果a = = b則c（a，b）為1。

實(shí)現(xiàn)：

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

如果你想了解更多關(guān)于 的解決方案，我們在另外的一篇文章中用實(shí)現(xiàn)了 and Text in ， 使用這個邏輯，我們可以將許多字符串比較算法歸結(jié)為簡單的遞歸關(guān)系，它使用 的基本公式

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.

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

闡明：

如果我們有兩個字符串s1="MICE"和s2="MINCE",最長的共同子序列是MI或者CE。但是，最長的公共子序列將是“MICE”，因?yàn)榻Y(jié)果子序列的元素不必是連續(xù)的順序。

遞歸關(guān)系與一般邏輯：

我們可以看到， 和LCS之間只有微小的差別，特別是移動成本。

在LCS中，我們沒有字符插入和字符刪除的成本，這意味著我們只計算字符替換（對角線移動）的成本，如果兩個當(dāng)前字符串字符a [i]和b [j]是相同的,則成本為1。

LCS的最終成本是2個字符串的最長子序列的長度，這正是我們所需要的。

Using this logic, we can boil down a lot of to which the base of the

使用這個邏輯，我們可以將許多字符串比較算法歸結(jié)為簡單的遞歸關(guān)系貪心算法 背包問題 c語言，它使用 的基本公式。

實(shí)現(xiàn)：

public class LCS {      public static void main(String[] args) {        String s1 = new String("Hillfinger");        String s2 = new String("Hilfiger");        int n = s1.length();        int m = s2.length();        int[][] solutionMatrix = new int[n+1][m+1];        for (int i = 0; i < n; i++) {            solutionMatrix[i][0] = 0;        }        for (int i = 0; i < m; i++) {            solutionMatrix[0][i] = 0;        }
        for (int i = 1; i <= n; i++) {            for (int j = 1; j <= m; j++) {                int max1, max2, max3;                max1 = solutionMatrix[i - 1][j];                max2 = solutionMatrix[i][j - 1];                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {                    max3 = solutionMatrix[i - 1][j - 1] + 1;                } else {                    max3 = solutionMatrix[i - 1][j - 1];                }                int tmp = Math.max(max1, max2);                solutionMatrix[i][j] = Math.max(tmp, max3);            }        }
        System.out.println("Length of longest continuous subsequence: " + solutionMatrix[n][m]);    }}

輸出：

Length of longest continuous subsequence: 8

8.利用動態(tài)規(guī)劃的其他問題

利用動態(tài)規(guī)劃可以解決很多問題，下面列舉了一些：

分區(qū)問題：給定一組整數(shù)，找出它是否可以分成兩個具有相等和的子集

子集和問題：給你一個正整數(shù)的數(shù)組及元素還有一個合計值，是否在數(shù)組中存在一個子集的的元素之和等于合計值。

硬幣變化問題：鑒于給定面額的硬幣無限供應(yīng)，找到獲得所需變化的不同方式的總數(shù)

k變量線性方程的所有可能的解：給定k個變量的線性方程，計算它的可能解的總數(shù)

找到醉漢不會從懸崖上掉下來的概率：給定一個線性空間代表距離懸崖的距離，讓你知道酒鬼從懸崖起始的距離，以及他向懸崖p前進(jìn)并遠(yuǎn)離懸崖1-p的傾向，計算出他的生存概率

9.結(jié)論

動態(tài)編程是一種工具，可以節(jié)省大量的計算時間，以換取更大的空間復(fù)雜性，這在很大程度上取決于您正在處理的系統(tǒng)類型，如果CPU時間很寶貴，您選擇耗費(fèi)內(nèi)存的解決方案，另一方面，如果您的內(nèi)存有限，則選擇更耗時的解決方案。