算法 之 动态规划（Dynamic Programming）

算法 之 动态规划（Dynamic Programming）

1. 基础概念

1.1 动态规划的定义

动态规划（Dynamic Programming，简称DP）是一种解决最优化问题的方法。它的核心思想是将问题分解为小的子问题，逐一解决子问题，并将结果保存以避免重复计算。动态规划通常包括以下几个步骤：

• 定义状态：确定每个子问题的状态。
• 状态转移方程：找到子问题之间的递推关系。
• 初始条件：为递推关系提供起始点。
• 求解结果：通过状态转移和保存结果，解决问题。

1.2 动态规划的特点

• 最优子结构：问题的最优解可以通过子问题的最优解构造。
• 重叠子问题：不同的子问题之间存在重复计算，动态规划通过记忆化或表格化技术避免这些重复。
• 递推性质：使用递归或迭代来逐步求解。

1.3 使用场景

• 最短路径问题（如Dijkstra、Floyd算法）。
• 字符串问题（如最长公共子序列、编辑距离）。
• 背包问题（0/1背包、完全背包等）。
• 区间问题（如矩阵链乘法、石子合并）。
• 博弈问题（如最优游戏策略）。

2. 实现与操作

2.1 核心操作实现

以下代码以经典的 0/1 背包问题为例，用 C 语言实现动态规划的基本操作。

#include <stdio.h> // 函数：解决0/1背包问题 int knapsack(int weights[], int values[], int n, int capacity) { int dp[n + 1][capacity + 1]; // 动态规划表 // 初始化动态规划表 for (int i = 0; i <= n; i++) { for (int w = 0; w <= capacity; w++) { dp[i][w] = 0; } } // 填表 for (int i = 1; i <= n; i++) { for (int w = 1; w <= capacity; w++) { if (weights[i - 1] <= w) { // 选择“取当前物品”或“不取当前物品”中的最大值 dp[i][w] = dp[i - 1][w] > dp[i - 1][w - weights[i - 1]] + values[i - 1] ? dp[i - 1][w] : dp[i - 1][w - weights[i - 1]] + values[i - 1]; } else { dp[i][w] = dp[i - 1][w]; // 当前物品无法放入 } } } return dp[n][capacity]; // 返回最大价值 } int main() { int weights[] = {1, 2, 3}; int values[] = {6, 10, 12}; int capacity = 5; // 背包容量 int n = sizeof(weights) / sizeof(weights[0]); printf("最大价值: %d\n", knapsack(weights, values, n, capacity)); return 0; } </stdio.h>

2.2 代码详解

• 初始化二维数组 dp 用于保存中间计算结果。
• 外层循环表示当前物品，内层循环表示当前背包容量。
• 通过状态转移方程实现递推：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])。
• 返回 dp[n][capacity] 即为最大价值。

3. 时间与空间复杂度分析

3.1 时间复杂度

时间复杂度为 O(n × capacity)，其中 n 是物品数量，capacity 是背包容量。原因是每个状态仅需计算一次。

3.2 空间复杂度

空间复杂度为 O(n × capacity)，可通过滚动数组优化为 O(capacity)。

4. 优缺点与局限性

4.1 优点

• 避免重复计算，提升效率。
• 适合解决具有最优子结构性质的问题。

4.2 缺点与局限性

• 需要额外的存储空间，可能导致内存消耗较大。
• 问题规模较大时，计算时间可能过长。

5. 常见应用场景

5.1 实际应用

下面是解决最长公共子序列（LCS）问题的代码示例：

#include <stdio.h> #include <string.h> // 函数：求最长公共子序列长度 int longestCommonSubsequence(char *str1, char *str2) { int m = strlen(str1), n = strlen(str2); int dp[m + 1][n + 1]; // 初始化 for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = 0; } } // 填表 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (str1[i - 1] == str2[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]; } } } return dp[m][n]; } int main() { char str1[] = "abcde"; char str2[] = "ace"; printf("最长公共子序列长度: %d\n", longestCommonSubsequence(str1, str2)); return 0; } </string.h></stdio.h>

6. 代码编译与运行

6.1 编译命令

使用以下命令编译代码：

gcc -o dp_example dp_example.c

6.2 测试用例

运行示例代码，验证结果：

    输入：weights = {1, 2, 3}, values = {6, 10, 12}, capacity = 5
    输出：最大价值: 22