算法学习-动态规划

2023-04-02 本文已影响0人麻辣香锅加特辣

动态规划（Dynamic Programming，简称DP）是一种常用于优化问题的算法思想，通常用于在计算机科学、经济学和数学等领域解决最优化问题。它的核心思想是将大问题划分为小问题，通过解决小问题来解决大问题。在本文中，我们将介绍动态规划的原理、经典案例以及示例代码。

原理

动态规划的核心思想是将一个问题分解成若干子问题，逐步求解子问题的最优解，从而得到原问题的最优解。动态规划包括以下几个步骤：

定义问题的状态：首先需要确定问题的状态，即描述问题的变量。状态可以是一个数值、一个数组、一个字符串或者更复杂的结构。
定义状态转移方程：状态转移方程是将问题的状态转移为下一个状态的函数。通过状态转移方程，可以计算出当前状态下的最优解。
确定初始状态：初始状态是问题的起点，它是无法通过状态转移方程计算出来的。因此，需要明确地给出初始状态。
确定终止状态：终止状态是问题的终点，它是已知的，通常是问题的目标状态。
求解最优解：通过状态转移方程和初始状态，可以递推计算出所有状态的最优解。最终，可以得到问题的最优解。

经典案例

1. Fibonacci数列

Fibonacci数列是一种经典的动态规划问题。其定义如下：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) （n>=2）

这个问题可以使用DP来解决。首先定义一个状态数组f，其中f[i]表示第i个Fibonacci数的值。由于f[0]和f[1]已知，所以可以先将它们填充到数组中。然后，从f[2]开始，根据状态转移方程计算出每个Fibonacci数的值，最后返回f[n]即可。

C++代码示例：

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    int f[n+1];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

2.最长公共子序列

最长公共子序列（Longest Common Subsequence，简称LCS）是另一个经典的动态规划问题。给定两个字符串X和Y，求它们的最长公共子序列。其中，子序列指的是从原序列中删除一些元素后得到的序列，不一定要相邻。
例如，对于字符串"ABCDGH"和" AEDFHR"，最长公共子序列为"ADH"，长度为3。

我们需要创建一个二维数组dp，其中dp[i][j]表示序列1的前i个字符和序列2的前j个字符之间的LCS的长度。然后，我们可以根据下面的递归式填充dp数组：
if (sequence1[i-1] == sequence2[j-1])
dp[i][j] = dp[i-1][j-1] + 1
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

最终结果将存储在dp[m][n]中，其中m是序列1的长度，n是序列2的长度。示例代码如下：

int lcs(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[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[m][n];
}

这段代码中，我们首先定义了两个字符串s1和s2，然后创建了一个二维向量dp。接下来，我们使用嵌套的for循环来填充dp数组，最后返回dp[m][n]作为最长公共子序列的长度。

3.背包问题

背包问题，是指有一个固定大小的背包，需要选择一些物品放入其中，每个物品有自己的重量和价值，要求选择的物品重量不超过背包容量，使得放入背包的物品总价值最大。

0/1背包问题：每个物品只能选择 0 或 1 个

定义状态 $f(i,j)$ 表示前 $i$ 个物品中，选择若干个放入重量不超过 $j$ 的背包中所能获得的最大价值。

需要考虑两种情况：
不选物品 $i$ ，此时 $f(i,j)=f(i-1,j)$ ；
选物品 $i$ ，此时 $f(i,j)=f(i-1,j-w_i)+v_i$ 。
最终，所求解即为 $f(n,W)$ 。

代码实现：

// w: 物品重量数组
// v: 物品价值数组
// c: 背包容量
int Knapsack01(vector<int>& w, vector<int>& v, int c)
{
    int n = w.size();
    // dp[i][j]表示将前i个物品放入容量为j的背包中所能获得的最大价值
    vector<vector<int>> dp(n+1, vector<int>(c+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= c; j++) {
            if (j < w[i-1]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]);
            }
        }
    }
    return dp[n][c];
}

int main()
{
    vector<int> w = {2, 3, 4, 5};
    vector<int> v = {3, 4, 5, 6};
    int c = 8;
    cout << "0/1 Knapsack Problem: " << Knapsack01(w, v, c) << endl;
    return 0;
}

完全背包问题：每个物品可以选择任意个

需要考虑两种情况：
不选物品 $i$ ，此时 $f(i,j)=f(i-1,j)$ ；
选物品 $i$ ，此时 $f(i,j)=f(i,j-w_i)+v_i$ 。
最终，所求解即为 $f(n,W)$ 。

// w: 物品重量数组
// v: 物品价值数组
// c: 背包容量
int KnapsackUnbounded(vector<int>& w, vector<int>& v, int c)
{
    int n = w.size();
    // dp[i][j]表示将前i个物品放入容量为j的背包中所能获得的最大价值
    vector<vector<int>> dp(n+1, vector<int>(c+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= c; j++) {
            if (j < w[i-1]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]]+v[i-1]);
            }
        }
    }
    return dp[n][c];
}

int main()
{
    vector<int> w = {2, 3, 4, 5};
    vector<int> v = {3, 4, 5, 6};
    int c = 8;
    cout << "Unbounded Knapsack Problem: " << KnapsackUnbounded(w, v, c) ;
    return 0;
}

总结一下，动态规划是解决许多优化问题的有用工具。通过将大问题分解为子问题，我们可以使用动态规划来找到最优解。在实践中，动态规划通常用于优化问题的解决方案，以便在较短的时间内找到最优解。在使用动态规划时，我们需要确定状态转移方程，并设计适当的数据结构来存储计算过程中产生的中间结果。