「程序员必须掌握的算法」动态规划「上篇」

缺乏、安全感 2023-10-15 20:06 1阅读 0赞

## 动态规划详解 ##

动态规划 (Dynamic Programming) 是一种算法思想，用于解决一些复杂的问题。本文将介绍动态规划的分类、概念和经典例题讲解。

### 动态规划的分类 ###

动态规划可以分为以下两种类型：

1.  0/1背包问题：该问题是动态规划的一种基本类型。在背包问题中，有n个物品可以放入容量为W的背包中，每个物品有自己的重量和价值。需要选择哪些物品能够最大化背包的总价值。
2.  最长公共子序列问题：该问题是另一种经典的动态规划类型，涉及到两个字符串，并找到这两个字符串之间的最长公共子序列。

### 动态规划的概念 ###

在解决动态规划问题时，我们需要定义以下概念：

1.  状态 (State)：问题中需要优化的变量，如背包问题中的容量，最长公共子序列问题中的字符串长度等。
2.  状态转移方程 (State Transition Equation)：描述状态之间的转移过程，即问题的递推关系。例如，在背包问题中，每个物品可以放入背包或不放入背包。因此，状态转移方程可以表示为： d p \[ i \] \[ j \] = max ⁡ ( d p \[ i − 1 \] \[ j \] , d p \[ i − 1 \] \[ j − w i \] + v i ) dp\[i\]\[j\] = \\max(dp\[i-1\]\[j\], dp\[i-1\]\[j-w\_i\]+v\_i) dp\[i\]\[j\]=max(dp\[i−1\]\[j\],dp\[i−1\]\[j−wi\]\+vi) 其中dp\[i\]\[j\]表示在使用前i个物品时，填满j容量的背包的最大价值。
3.  初始状态 (Initial State)：问题的初始条件，通常为问题规模最小的情况下的答案。在背包问题中，初始状态为dp\[0\]\[0\]=0。
4.  边界状态 (Boundary State)：问题的边界条件，在状态转移过程中需要特别处理的状态。在背包问题中，背包的容量不能为负数，因此需要在状态转移方程中特别处理。

### 经典例题讲解 ###

下面我们将分别介绍0/1背包问题和最长公共子序列问题的解法。

#### 1. 0/1背包问题 ####

题目描述：有n个物品和一个容量为W的背包。第i个物品的重量为wi，价值为vi。现在，需要选择一些物品放入背包，使得放入的物品的总重量不超过W，且总价值最大。求最大价值。

解题思路：定义状态dp\[i\]\[j\]为在使用前i个物品时，填满j容量的背包的最大价值。状态转移方程如下所示： d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j \] , j < w i max ⁡ ( d p \[ i − 1 \] \[ j \] , d p \[ i − 1 \] \[ j − w i \] + v i ) , j ≥ w i dp\[i\]\[j\] = \\begin\{cases\}dp\[i-1\]\[j\],&j<w\_i\\\\ \\max(dp\[i-1\]\[j\], dp\[i-1\]\[j-w\_i\]+v\_i),&j\\ge w\_i\\end\{cases\} dp\[i\]\[j\]=\{ dp\[i−1\]\[j\],max(dp\[i−1\]\[j\],dp\[i−1\]\[j−wi\]\+vi),j<wij≥wi 其中dp\[i-1\]\[j\]表示不放入第i个物品的最大价值，dp\[i-1\]\[j-w\[i\]\]+v\[i\]表示将第i个物品加入背包的最大价值。需要注意的是，如果当前背包容量小于物品的重量，就不能将该物品放入背包。因此，需要特别处理背包容量小于物品重量的情况。

代码实现：

int dp[101][1001];
    int weight[101], value[101];
    
    int knapSack(int n, int w)
    {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= w; j++) {
                if (j < weight[i]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
                }
            }
        }
        return dp[n][w];
    }

#### 2. 最长公共子序列问题 ####

题目描述：给定两个字符串A和B，找到它们的最长公共子序列 (LCS)。

解题思路：定义状态dp\[i\]\[j\]为字符串A的前i个字符和字符串B的前j个字符的LCS长度。状态转移方程如下所示：

d p \[ i \] \[ j \] = \{ 0 , i = 0 或 j = 0 d p \[ i − 1 \] \[ j − 1 \] + 1 , A i = B j max ⁡ ( d p \[ i − 1 \] \[ j \] , d p \[ i \] \[ j − 1 \] ) , A i ≠ B j dp\[i\]\[j\] = \\begin\{cases\}0,&i=0\\text\{或\}j=0\\\\ dp\[i-1\]\[j-1\]+1,&A\_i=B\_j\\\\ \\max(dp\[i-1\]\[j\], dp\[i\]\[j-1\]),&A\_i\\neq B\_j\\end\{cases\} dp\[i\]\[j\]=⎩⎨⎧0,dp\[i−1\]\[j−1\]\+1,max(dp\[i−1\]\[j\],dp\[i\]\[j−1\]),i=0或j=0Ai=BjAi=Bj

当A\[i-1\]等于B\[j-1\]时，dp\[i\]\[j\]等于dp\[i-1\]\[j-1\]+1，表示A和B中的相同字符加上它们前面的LCS。当它们不相等时，LCS为它们前面的LCS的最大值，即dp\[i-1\]\[j\]和dp\[i\]\[j-1\]的最大值。

代码实现：

int dp[1001][1001];
    string A, B;
    
    int LCS(int n, int m)
    {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else if (A[i-1] == B[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }

### 结语 ###

动态规划是一种非常重要的算法思想，它通常用于解决复杂的问题。在应用动态规划解决问题时，需要注意定义状态、状态转移方程、初始状态和边界状态等概念。对于不同类型的动态规划问题，需要采用不同的解决方法。希望本文能够帮助读者加深对动态规划的理解。