动态规划（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]);
else
dp[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;
else
L[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--;
else
j--;
}
// 打印LCS
printf("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，实际使用时需要注意这一点。
