算法之动态规划

动态规划

• 动态规划
• • 1. 核心思想
  • 2. 基本步骤
  • 3. 关键概念
  • • 3.1 基本概念
    • 3.2 优化技巧
  • 4. 常见应用场景
  • 5. 典型案例
  • • 5.1 斐波那契数列
    • 5.2 背包问题
    • • 5.2.1 0-1背包问题
      • 5.2.2 完全背包问题
    • 5.3 最短路径——Floyd算法
    • 5.4 最长公共子序列（LCS）
    • 5.5 最长递增子序列（LIS）
  • 6. 解题技巧与思路
  • 7. 总结

动态规划

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");
            else
                printf("%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;
            else
                dp[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;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    
    // 构造LCS
    int 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