算法--动态规划

news/2024/5/20 20:24:32

动态规划（Dynamic Programming, DP）是一种算法设计技巧，用于解决具有重叠子问题和最优子结构性质的问题。通过将原问题分解为相对简单的子问题的方式来求解复杂问题，动态规划避免了计算重复子问题，从而提高了算法的效率。

动态规划的关键特点包括：

重叠子问题：在求解过程中，相同的子问题会被多次计算。动态规划通过存储这些子问题的解（通常是在一个表格中），每个子问题只解决一次，以避免不必要的计算。
最优子结构：一个问题的最优解包含其子问题的最优解。这意味着可以通过组合子问题的最优解来构造原问题的最优解。
状态转移方程：动态规划算法的核心，它描述了问题的状态如何从一个状态转移到另一个状态。状态转移方程通常取决于当前决策和相应的子问题解。

动态规划的步骤通常包括：

定义状态：确定问题的状态，以及状态之间的关系。
确定状态转移方程：找出状态之间如何转移的规则。
初始化条件：确定初始状态的值。
计算顺序：确定计算状态的顺序，确保在计算当前状态时，所需的子状态已经计算过。
构造最优解：根据计算出的状态值，构造问题的最优解。
动态规划广泛应用于各种领域，包括但不限于：

最短路径问题：如Dijkstra算法和Floyd-Warshall算法。
序列对齐问题：如生物信息学中的序列对齐。
资源分配问题：如背包问题。
字符串编辑距离：如计算两个字符串之间的最小编辑距离。
最长公共子序列：找出两个序列共有的最长子序列。

动态规划是解决优化问题的强大工具，但它要求问题具有重叠子问题和最优子结构的特性。正确识别和定义这些特性是应用动态规划成功的关键。

0-1背包问题
0-1背包问题是动态规划中的经典问题。给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，选择其中若干个（也即每种物品可以选择0个或1个），设计选择方案使得物品的总价值最高。
以下是使用动态规划解决0-1背包问题的C语言实现：

#include <stdio.h>
#include <stdlib.h>// 返回两个整数中的最大值
int max(int a, int b) {return (a > b) ? a : b;
}// 动态规划解决0-1背包问题
// 参数：W为背包最大容量，wt为物品重量数组，val为物品价值数组，n为物品数量
int knapSack(int W, int wt[], int val[], int n) {int i, w;// 创建一个二维数组dp，其中dp[i][w]表示在前i个物品中，能够装入容量为w的背包中的最大价值int **dp = (int **)malloc((n + 1) * sizeof(int *));for (i = 0; i <= n; i++) {dp[i] = (int *)malloc((W + 1) * sizeof(int));}// 填充表格for (i = 0; i <= n; i++) {for (w = 0; w <= W; w++) {if (i == 0 || w == 0)dp[i][w] = 0;else if (wt[i - 1] <= w)dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);elsedp[i][w] = dp[i - 1][w];}}// 存储结果int result = dp[n][W];// 释放dp数组for (i = 0; i <= n; i++) {free(dp[i]);}free(dp);return result;
}// 测试代码
int main() {int val[] = {60, 100, 120};int wt[] = {10, 20, 30};int W = 50;int n = sizeof(val) / sizeof(val[0]);printf("背包中物品的最大价值为：%d", knapSack(W, wt, val, n));return 0;
}

这段代码首先定义了一个max函数，用于返回两个整数中的最大值。knapSack函数是动态规划解决0-1背包问题的核心，它创建了一个二维数组dp，其中dp[i][w]表示在前i个物品中，能够装入容量为w的背包中的最大价值。通过填充这个表格，最终在dp[n][W]中得到了在给定物品和背包容量限制下的最大价值。最后，函数释放了dp数组所占用的内存，并返回了最大价值结果。

最长公共子序列问题
最长公共子序列（Longest Common Subsequence, LCS）问题是寻找两个序列共有的最长子序列的长度，这个子序列不需要在原序列中是连续的。以下是使用动态规划解决最长公共子序列问题的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 返回两个整数中的最大值
int max(int a, int b) {return (a > b) ? a : b;
}// 动态规划解决LCS问题
int lcs(char *X, char *Y, int m, int n) {int L[m+1][n+1];int i, j;// 构建L[m+1][n+1]，以便保存LCS的长度for (i = 0; i <= m; i++) {for (j = 0; j <= n; j++) {if (i == 0 || j == 0)L[i][j] = 0;else if (X[i-1] == Y[j-1])L[i][j] = L[i-1][j-1] + 1;elseL[i][j] = max(L[i-1][j], L[i][j-1]);}}// L[m][n]包含了X[0..m-1]和Y[0..n-1]的LCS的长度return L[m][n];
}// 打印LCS，这是一个辅助函数
void printLCS(char *X, char *Y, int m, int n) {int index = lcs(X, Y, m, n);char lcs[index+1];lcs[index] = '\0'; // 设置字符串的终止符int i = m, j = n;while (i > 0 && j > 0) {if (X[i-1] == Y[j-1]) {lcs[index-1] = X[i-1]; // 如果当前字符在LCS中i--; j--; index--;     // 减少值}else if (L[i-1][j] > L[i][j-1])i--;elsej--;}// 打印LCSprintf("LCS of %s and %s is %s\n", X, Y, lcs);
}// 测试代码
int main() {char X[] = "AGGTAB";char Y[] = "GXTXAYB";int m = strlen(X);int n = strlen(Y);printf("Length of LCS is %d\n", lcs(X, Y, m, n));// 如果需要打印LCS，取消注释下面的行// printLCS(X, Y, m, n);return 0;
}

这段代码首先定义了一个max函数，用于返回两个整数中的最大值。lcs函数是动态规划解决LCS问题的核心，它创建了一个二维数组L，其中L[i][j]表示字符串X[0…i-1]和Y[0…j-1]的LCS的长度。通过填充这个表格，最终在L[m][n]中得到了两个字符串的LCS的长度。

请注意，上述代码中的printLCS函数用于打印LCS，但由于它依赖于L数组，而L数组在lcs函数中是局部变量，直接使用printLCS函数可能会导致编译错误。为了使printLCS函数正常工作，需要对代码进行适当的修改，以便能够访问或重新计算L数组的值。这里提供的printLCS函数主要是为了展示如何根据L数组回溯找到LCS，实际使用时需要注意这一点。