动态规划基础学习理论

一、动态规划的基本概念

1.1 什么是动态规划

动态规划是一种算法设计范式，由美国数学家理查德·贝尔曼在20世纪50年代提出。它主要应用于具有重叠子问题和最优子结构性质的问题。动态规划方法通常用来求解最优化问题，这类问题可以有多个可行解，每个解都对应一个值，我们希望找到具有最优值（最大值或最小值）的解。

动态规划的核心思想是：将待求解的问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划的子问题往往不是相互独立的，因此需要保存已解决的子问题的答案，避免重复计算。

1.2 动态规划适用的条件

一个问题适合用动态规划求解，必须满足以下两个关键特性：

1. 最优子结构：一个问题的最优解包含其子问题的最优解。也就是说，可以通过子问题的最优解构造出原问题的最优解。

2. 重叠子问题：在递归求解过程中，会反复遇到相同的子问题，而不是生成全新的子问题。

1.3 动态规划与分治法的比较

二、动态规划的基本步骤

动态规划算法的设计通常遵循以下步骤：

1. 定义状态：确定问题的状态，并用状态变量表示

2. 建立状态转移方程：确定状态之间的转移关系

3. 确定初始条件和边界条件

4. 确定计算顺序：自底向上或自顶向下

5. 计算并输出结果

三、经典问题解析与C语言实现

3.1 斐波那契数列

斐波那契数列是动态规划最经典的入门例子，它完美展示了重叠子问题和如何通过存储中间结果避免重复计算。

3.1.1 问题描述

斐波那契数列的定义如下：

• F(0) = 0

• F(1) = 1

• F(n) = F(n-1) + F(n-2) (n ≥ 2)

3.1.2 递归解法（低效）

#include <stdio.h> // 递归解法 - 时间复杂度O(2^n)，非常低效 int fibonacci_recursive(int n) { if (n <= 1) { return n; } return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2); }

递归的重复计算问题

• 计算F(5)时，F(3)被计算了2次

• 计算F(4)时，F(2)被计算了3次

• 总计算量呈指数级增长

3.1.3 动态规划解法

#include <stdio.h> #include <stdlib.h> // 动态规划解法 - 时间复杂度O(n)，空间复杂度O(n) int fibonacci_dp(int n) { if (n <= 1) { return n; } int *dp = (int *)malloc((n + 1) * sizeof(int)); if (dp == NULL) { printf("内存分配失败\n"); return -1; } // 初始条件 dp[0] = 0; dp[1] = 1; // 状态转移 for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } int result = dp[n]; free(dp); return result; } // 优化空间复杂度为O(1)的动态规划解法 int fibonacci_dp_optimized(int n) { if (n <= 1) { return n; } int prev2 = 0; // F(i-2) int prev1 = 1; // F(i-1) int current; // F(i) for (int i = 2; i <= n; i++) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } return current; } int main() { int n = 10; printf("计算斐波那契数列 F(%d):\n", n); printf("递归解法: %d\n", fibonacci_recursive(n)); printf("动态规划解法: %d\n", fibonacci_dp(n)); printf("优化空间的动态规划解法: %d\n", fibonacci_dp_optimized(n)); return 0; }

• 时间复杂度：O(n)

• 空间复杂度：从O(n)优化到O(1)

3.2 爬楼梯问题

3.2.1 问题描述

假设你正在爬楼梯。需要 n 阶你才能到。你有达楼顶。每次你可以爬 1 或 2 个台阶多少种不同的方法可以爬到楼顶？

状态定义

设 dp[i] 表示爬到第 i 阶楼梯的不同方法数。

状态转移方程

要到达第 i 阶楼梯，有两种方式：

1. 从第 i-1 阶爬 1 阶上来

2. 从第 i-2 阶爬 2 阶上来

因此，状态转移方程为：

dp[i] = dp[i-1] + dp[i-2] (i ≥ 3)

边界条件

dp[1] = 1 // 爬到第1阶有1种方法 dp[2] = 2 // 爬到第2阶有2种方法

完整实现

#include <stdio.h> #include <stdlib.h> // 动态规划解法 int climbStairs(int n) { if (n <= 2) { return n; } // 创建DP数组 int *dp = (int *)malloc((n + 1) * sizeof(int)); if (dp == NULL) { printf("内存分配失败\n"); return -1; } // 初始化边界条件 dp[1] = 1; // 爬到第1阶只有1种方法：爬1阶 dp[2] = 2; // 爬到第2阶有2种方法：(1,1) 或 (2) // 状态转移 for (int i = 3; i <= n; i++) { // 到达第i阶的方法数 = 到达第i-1阶的方法数 + 到达第i-2阶的方法数 dp[i] = dp[i - 1] + dp[i - 2]; // 详细解释： // 1. 从第i-1阶爬1阶上来，有dp[i-1]种方法 // 2. 从第i-2阶爬2阶上来，有dp[i-2]种方法 // 总方法数就是这两者之和 } int result = dp[n]; // 打印中间过程（调试用） printf("DP数组: "); for (int i = 1; i <= n; i++) { printf("%d ", dp[i]); } printf("\n"); free(dp); return result; }

时间复杂度分析：

• 时间复杂度：O(n)，只需一次遍历

• 空间复杂度：O(n)，需要长度为n+1的数组

3.3 背包问题

背包问题是动态规划的经典应用，分为0-1背包和完全背包两种主要类型。

3.3.1 0-1背包问题

问题描述

有一个容量为C的背包和N件物品，每件物品有重量w[i]和价值v[i]。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且总价值最大。

动态规划解法

#include <stdio.h> #include <stdlib.h> // 0-1背包问题的动态规划解法 int knapsack_01(int C, int N, int w[], int v[]) { // 创建二维DP数组 int **dp = (int **)malloc((N + 1) * sizeof(int *)); for (int i = 0; i <= N; i++) { dp[i] = (int *)malloc((C + 1) * sizeof(int)); } // 初始化：没有物品或背包容量为0时，最大价值为0 for (int i = 0; i <= N; i++) { dp[i][0] = 0; } for (int j = 0; j <= C; j++) { dp[0][j] = 0; } // 动态规划填表 for (int i = 1; i <= N; i++) { for (int j = 1; j <= C; j++) { if (j < w[i - 1]) { // 当前物品重量大于背包剩余容量，不能放入 dp[i][j] = dp[i - 1][j]; } else { // 可以选择放入或不放入当前物品，取最大值 int not_put = dp[i - 1][j]; int put = dp[i - 1][j - w[i - 1]] + v[i - 1]; dp[i][j] = (not_put > put) ? not_put : put; } } } int result = dp[N][C]; // 输出具体选择了哪些物品 printf("选择的物品: "); int j = C; for (int i = N; i > 0; i--) { if (dp[i][j] != dp[i - 1][j]) { printf("%d ", i); j -= w[i - 1]; } } printf("\n"); // 释放内存 for (int i = 0; i <= N; i++) { free(dp[i]); } free(dp); return result; } // 空间优化版本（一维数组） int knapsack_01_optimized(int C, int N, int w[], int v[]) { int *dp = (int *)malloc((C + 1) * sizeof(int)); // 初始化 for (int j = 0; j <= C; j++) { dp[j] = 0; } // 动态规划 for (int i = 1; i <= N; i++) { // 注意：这里需要从后向前遍历，确保每个物品只被考虑一次 for (int j = C; j >= w[i - 1]; j--) { int not_put = dp[j]; int put = dp[j - w[i - 1]] + v[i - 1]; dp[j] = (not_put > put) ? not_put : put; } } int result = dp[C]; free(dp); return result; } int main() { int C = 10; // 背包容量 int N = 5; // 物品数量 int w[] = {2, 3, 4, 5, 9}; // 物品重量 int v[] = {3, 4, 5, 8, 10}; // 物品价值 printf("0-1背包问题（容量=%d，物品数=%d）\n", C, N); printf("物品重量: "); for (int i = 0; i < N; i++) { printf("%d ", w[i]); } printf("\n"); printf("物品价值: "); for (int i = 0; i < N; i++) { printf("%d ", v[i]); } printf("\n"); int max_value = knapsack_01(C, N, w, v); printf("最大价值（二维DP）: %d\n", max_value); max_value = knapsack_01_optimized(C, N, w, v); printf("最大价值（一维DP优化）: %d\n", max_value); return 0; }

3.3.2 完全背包问题

问题描述

与0-1背包问题类似，但每种物品都有无限件可用。

关键区别：

• 0-1背包：每种物品只有1件（选或不选）

• 完全背包：每种物品有无限件（可选0件、1件、2件...）

问题分析

1. 与0-1背包的本质区别

为了深入理解完全背包，我们先对比两种背包问题的区别：

0-1背包的状态转移方程：

dp[i][j] = max(dp[i-1][j], // 不选第i件物品 dp[i-1][j-w[i]] + v[i]) // 选第i件物品（只能选一次）

完全背包的状态转移方程：

dp[i][j] = max(dp[i-1][j], // 不选第i件物品 dp[i][j-w[i]] + v[i]) // 选第i件物品（可以选多次）

关键区别：第二个状态转移项中，从dp[i][j-w[i]]转移，而不是dp[i-1][j-w[i]]。这意味着在考虑是否选择第i件物品时，已经考虑了可能已经选择了多个该物品的情况。

算法实现详解

1. 二维DP解法

#include <stdio.h> #include <stdlib.h> // 完全背包问题的朴素二维DP解法 int knapsack_complete_2d(int C, int N, int w[], int v[]) { // 创建二维DP数组 // dp[i][j]表示考虑前i种物品，背包容量为j时的最大价值 int **dp = (int **)malloc((N + 1) * sizeof(int *)); for (int i = 0; i <= N; i++) { dp[i] = (int *)malloc((C + 1) * sizeof(int)); } // 初始化：没有物品时，价值为0 for (int j = 0; j <= C; j++) { dp[0][j] = 0; } printf("完全背包问题（容量=%d，物品种类=%d）\n", C, N); printf("物品重量："); for (int i = 0; i < N; i++) printf("%d ", w[i]); printf("\n物品价值："); for (int i = 0; i < N; i++) printf("%d ", v[i]); printf("\n\n"); // 动态规划填表 for (int i = 1; i <= N; i++) { for (int j = 0; j <= C; j++) { // 不选择第i种物品 dp[i][j] = dp[i - 1][j]; // 选择第i种物品（如果可以的话） // 注意：这里是完全背包的关键！与0-1背包的区别 if (j >= w[i - 1]) { // 这里使用dp[i][j-w[i-1]]而不是dp[i-1][j-w[i-1]] // 这允许同一物品被选择多次 int take = dp[i][j - w[i - 1]] + v[i - 1]; if (take > dp[i][j]) { dp[i][j] = take; } } } } // 打印DP表（帮助理解） printf("二维DP表：\n"); printf("容量\\物品 "); for (int i = 0; i <= N; i++) { if (i == 0) printf("无物品 "); else printf("物品%-2d ", i); } printf("\n"); for (int j = 0; j <= C; j++) { printf("容量=%-3d: ", j); for (int i = 0; i <= N; i++) { printf("%4d ", dp[i][j]); } printf("\n"); } printf("\n"); int result = dp[N][C]; // 回溯找出选择的物品和数量 printf("最优选择方案：\n"); int remaining_capacity = C; for (int i = N; i >= 1; i--) { int count = 0; while (remaining_capacity >= w[i - 1] && dp[i][remaining_capacity] == dp[i][remaining_capacity - w[i - 1]] + v[i - 1]) { count++; remaining_capacity -= w[i - 1]; } if (count > 0) { printf(" 物品%d：选择%d件\n", i, count); } } printf("总价值：%d\n", result); // 释放内存 for (int i = 0; i <= N; i++) { free(dp[i]); } free(dp); return result; }

3.4 最长公共子序列（LCS）

3.4.1 问题描述

给定两个序列X和Y，找出它们的最长公共子序列的长度。子序列不要求连续，但必须保持相对顺序。

3.4.2 动态规划解法

#include <stdio.h> #include <stdlib.h> #include <string.h> // 最长公共子序列的动态规划解法 int longestCommonSubsequence(char *text1, char *text2) { int m = strlen(text1); int n = strlen(text2); // 创建二维DP数组 int **dp = (int **)malloc((m + 1) * sizeof(int *)); for (int i = 0; i <= m; i++) { dp[i] = (int *)malloc((n + 1) * sizeof(int)); } // 初始化边界条件 for (int i = 0; i <= m; i++) { dp[i][0] = 0; } for (int j = 0; j <= n; j++) { dp[0][j] = 0; } // 动态规划填表 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; } else { dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1]; } } } int result = dp[m][n]; // 输出LCS（重建路径） printf("最长公共子序列: "); char *lcs = (char *)malloc((result + 1) * sizeof(char)); lcs[result] = '\0'; int i = m, j = n, index = result - 1; while (i > 0 && j > 0) { if (text1[i - 1] == text2[j - 1]) { lcs[index] = text1[i - 1]; i--; j--; index--; } else if (dp[i - 1][j] > dp[i][j - 1]) { i--; } else { j--; } } printf("%s\n", lcs); free(lcs); // 释放内存 for (int i = 0; i <= m; i++) { free(dp[i]); } free(dp); return result; } int main() { char text1[] = "ABCBDAB"; char text2[] = "BDCABA"; printf("序列1: %s\n", text1); printf("序列2: %s\n", text2); int lcs_length = longestCommonSubsequence(text1, text2); printf("最长公共子序列长度: %d\n", lcs_length); return 0; }

3.5 股票买卖问题

3.5.1 问题描述

给定一个数组，其中第i个元素是第i天股票的价格。设计算法来计算最大利润。

3.5.2 动态规划解法

#include <stdio.h> #include <stdlib.h> // 只能进行一次交易的最大利润 int maxProfit_one_transaction(int prices[], int n) { if (n <= 1) return 0; int min_price = prices[0]; int max_profit = 0; for (int i = 1; i < n; i++) { if (prices[i] < min_price) { min_price = prices[i]; } else { int profit = prices[i] - min_price; if (profit > max_profit) { max_profit = profit; } } } return max_profit; } // 可以进行无限次交易的最大利润 int maxProfit_unlimited(int prices[], int n) { int max_profit = 0; for (int i = 1; i < n; i++) { if (prices[i] > prices[i - 1]) { max_profit += prices[i] - prices[i - 1]; } } return max_profit; } // 最多可以进行两次交易的最大利润 int maxProfit_two_transactions(int prices[], int n) { if (n <= 1) return 0; // 创建四个数组 int *first_buy = (int *)malloc(n * sizeof(int)); int *first_sell = (int *)malloc(n * sizeof(int)); int *second_buy = (int *)malloc(n * sizeof(int)); int *second_sell = (int *)malloc(n * sizeof(int)); // 初始化 first_buy[0] = -prices[0]; first_sell[0] = 0; second_buy[0] = -prices[0]; second_sell[0] = 0; for (int i = 1; i < n; i++) { first_buy[i] = (first_buy[i - 1] > -prices[i]) ? first_buy[i - 1] : -prices[i]; first_sell[i] = (first_sell[i - 1] > first_buy[i - 1] + prices[i]) ? first_sell[i - 1] : first_buy[i - 1] + prices[i]; second_buy[i] = (second_buy[i - 1] > first_sell[i - 1] - prices[i]) ? second_buy[i - 1] : first_sell[i - 1] - prices[i]; second_sell[i] = (second_sell[i - 1] > second_buy[i - 1] + prices[i]) ? second_sell[i - 1] : second_buy[i - 1] + prices[i]; } int result = second_sell[n - 1]; free(first_buy); free(first_sell); free(second_buy); free(second_sell); return result; } int main() { int prices[] = {3, 3, 5, 0, 0, 3, 1, 4}; int n = sizeof(prices) / sizeof(prices[0]); printf("股票价格: "); for (int i = 0; i < n; i++) { printf("%d ", prices[i]); } printf("\n"); printf("只允许一次交易的最大利润: %d\n", maxProfit_one_transaction(prices, n)); printf("允许无限次交易的最大利润: %d\n", maxProfit_unlimited(prices, n)); printf("最多允许两次交易的最大利润: %d\n", maxProfit_two_transactions(prices, n)); return 0; }

4.1. 自底向上（迭代）（dp核心）

// 自底向上动态规划示例 int fibonacci_bottom_up(int n) { if (n <= 1) { return n; } int dp[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }

动态规划不仅能够帮助我们解决具体的算法问题，还培养了我们将复杂问题分解为简单子问题的思维习惯，感谢观看