动态规划算法通过子问题重叠和最优子结构优化问题求解效率。最长公共子序列、0-1 背包问题和扩展欧几里得算法都是常见的动态规划问题，可使用 c 语言实现。实战案例中，动态规划用于查找网格中从左上角到右下角路径上的最大和，通过创建表格存储子问题解决方案，以避免重复计算。
C语言算法问答集：破解动态规划问题
动态规划是一种用于解决特定问题的算法范例，它通过分解问题为子问题并存储子问题的解决方案来优化效率。对于初学者来说，理解动态规划的概念和实施方式至关重要。
核心概念
立即学习“C语言免费学习笔记（深入）”；
- 子问题重叠：动态规划问题通常具有重叠子问题，即解决较小子问题是解决较大问题的重要组成部分。
- 最优子结构：问题的最优解可以通过其子问题的最优解构建。
- 记忆化：存储子问题的解决方案，以避免重新计算。
常见问题
下面列出了一些常见的动态规划问题及其 C 语言解决方案：
最长公共子序列（LCS）
int lcs(char *X, char *Y) {
int m = strlen(X);
int n = strlen(Y);
int L[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int 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]);
}
}
return L[m][n];
}0-1 背包
int knapsack(int weights[], int values[], int W, int n) {
int K[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= W; j++) {
if (i == 0 || j == 0)
K[i][j] = 0;
else if (weights[i - 1] <= j)
K[i][j] = max(values[i - 1] + K[i - 1][j - weights[i - 1]], K[i - 1][j]);
else
K[i][j] = K[i - 1][j];
}
}
return K[n][W];
}扩展欧几里得算法（GCD）
int gcdExtended(int a, int b) {
if (b == 0)
return a;
return gcdExtended(b, a % b);
}实战案例
假设我们有一个网格，其中每个单元格包含一个整数。我们的目标是找到从左上角到右下角的路径，使得路径上单元格的和最大。我们只能向下或向右移动。
我们可以使用动态规划来解决这个问题。我们定义一个表 dp，其中 dp[i, j] 表示从左上角到单元格 (i, j) 的最大路径和。以下是如何使用 C 语言实现该算法：
#includeint main() { int grid[4][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16} }; int dp[4][4]; // 表格 dp dp[0][0] = grid[0][0]; // 初始化左上角单元格 for (int i = 1; i < 4; i++) { dp[0][i] = dp[0][i - 1] + grid[0][i]; // 初始化顶部行 } for (int i = 1; i < 4; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; // 初始化左侧列 } for (int i = 1; i < 4; i++) { for (int j = 1; j < 4; j++) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; // 更新表格 } } printf("从左上角到右下角的最大路径和为 %d\n", dp[3][3]); // 打印结果 return 0; }
输出：
从左上角到右下角的最大路径和为 49
