当前位置：首页 > article >正文

动态规划(c基础)

article 2024/12/2 14:04:55

动态规划的基本概念
- 定义：动态规划是一种用于解决优化问题的算法策略。它把一个复杂的问题分解为一系列相互关联的子问题，通过求解子问题的最优解来构建原问题的最优解。
- 核心要素：
  - 状态（State）：状态是对问题在某一时刻或某一阶段的描述。例如，在计算斐波那契数列时，第 n 个数就是一个状态，我们可以用一个数组dp[n]来表示这个状态，其中dp[i]表示斐波那契数列的第 i 个数。
  - 状态转移方程（State - Transfer Equation）：它描述了如何从一个或多个已知的状态推导出另一个状态。比如在斐波那契数列中，状态转移方程为dp[i] = dp[i - 1] + dp[i - 2]，这表示要计算第 i 个斐波那契数，需要知道第 i - 1 个和第 i - 2 个斐波那契数。
  - 边界条件（Boundary Condition）：这是问题的最基础、最简单的情况，用于初始化动态规划数组。例如，在斐波那契数列中，dp[0] = 0，dp[1] = 1就是边界条件。
动态规划的解题步骤
- 步骤一：定义状态
  - 根据问题的特点来定义状态。例如，在背包问题中，如果有 n 个物品和容量为 C 的背包，我们可以定义状态dp[i][j]表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值。
  - 状态的定义应该能够完整地描述问题的某个阶段，并且方便后续的状态转移方程推导。
- 步骤二：确定状态转移方程
  - 分析问题的逻辑，找出状态之间的递推关系。以 0 - 1 背包问题为例，对于每个物品 i，有两种选择：放入背包或者不放入背包。
  - 如果不放入背包，那么dp[i][j] = dp[i - 1][j]；如果放入背包，那么dp[i][j] = dp[i - 1][j - w[i]] + v[i]（其中w[i]是第 i 个物品的重量，v[i]是第 i 个物品的价值）。所以状态转移方程为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])。
  - 确定状态转移方程需要对问题进行深入的思考和分析，有时候可能需要通过数学推导或者实际例子来辅助理解。
- 步骤三：确定边界条件
  - 边界条件是动态规划的基础。例如，在背包问题中，当没有物品（i = 0）或者背包容量为 0（j = 0）时，dp[0][j] = 0（没有物品，背包价值为 0），dp[i][0] = 0（背包容量为 0，无法放入物品，价值为 0）。
  - 正确地确定边界条件可以保证动态规划算法的正确启动和后续计算的准确性。
- 步骤四：计算顺序
  - 按照状态的依赖关系确定计算顺序。一般来说，状态的计算是从简单到复杂，从边界条件开始逐步推导。例如，在计算斐波那契数列的动态规划数组时，我们先计算dp[0]和dp[1]（边界条件），然后按照dp[2]、dp[3]…… 的顺序依次计算，因为dp[i]依赖于dp[i - 1]和dp[i - 2]。
  - 在二维数组的情况下，通常是按照行或者列的顺序进行计算，例如在背包问题中，我们可以先固定物品数量 i，从 i = 0 开始逐步增加，对于每个 i，再从背包容量 j = 0 开始逐步增加来计算dp[i][j]。
动态规划的应用场景和示例
- 应用场景：
  - 最优子结构问题：如果一个问题的最优解包含子问题的最优解，那么这个问题可能适合用动态规划解决。例如，最长公共子序列（LCS）问题，两个序列的最长公共子序列的最优解可以通过子序列的最长公共子序列来构建。
  - 重叠子问题：当一个问题可以分解为多个子问题，并且这些子问题会被重复计算时，动态规划可以避免重复计算，提高效率。例如，计算斐波那契数列时，如果使用递归方法，会有大量的重复计算，而动态规划可以通过记录已经计算过的状态来避免这种情况。
- 示例：最长公共子序列（LCS）问题
  - 问题描述：给定两个序列X = [x1, x2, …, xm]和Y = [y1, y2, …, yn]，求这两个序列的最长公共子序列的长度。
  - 状态定义：设dp[i][j]表示序列X的前 i 个元素和序列Y的前 j 个元素的最长公共子序列的长度。
  - 状态转移方程：
    - 如果xi = yj，那么dp[i][j] = dp[i - 1][j - 1] + 1，因为找到了一个新的公共元素，最长公共子序列长度加 1。
    - 如果xi ≠ yj，那么dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])，即取X的前 i - 1 个元素和Y的前 j 个元素的最长公共子序列长度，或者X的前 i 个元素和Y的前 j - 1 个元素的最长公共子序列长度中的最大值。
  - 边界条件：
    - 当i = 0或者j = 0时，dp[i][j] = 0，因为空序列的最长公共子序列长度为 0。
  - C 语言示例代码：

隐藏过程

复制

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int longestCommonSubsequence(char* X, char* Y) {
    int m = strlen(X);
    int n = strlen(Y);
    int** dp = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int*)malloc((n + 1) * sizeof(int));
    }
    // 初始化边界条件
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            }
        }
    }
    // 计算dp数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1])? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }
    int result = dp[m][n];
    // 释放动态分配的内存
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);
    return result;
}

int main() {
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
    int lcsLength = longestCommonSubsequence(X, Y);
    printf("最长公共子序列长度为：%d\n", lcsLength);
    return 0;
}

动态规划是一种强大的算法策略，通过合理地定义状态、推导状态转移方程、确定边界条件和计算顺序，可以高效地解决许多复杂的优化问题。

查看全文

http://www.kler.cn/a/418543.html