【C++】动态规划从入门到精通

发布于：2025-03-20 ⋅ 阅读:(21) ⋅ 点赞:(0)

一、动态规划基础概念详解

什么是动态规划
动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为重叠子问题，并存储子问题解以避免重复计算的优化算法。它适用于具有以下两个关键性质的问题：

最优子结构：问题的最优解包含子问题的最优解

重叠子问题：不同决策序列会重复求解相同的子问题

下面用一些例子（由浅入深）了解动态规划

1.1 斐波那契数列递归实现解析

int fib(int n) {
    if(n <= 1) return n;          // 基准条件：F(0)=0, F(1)=1
    return fib(n-1) + fib(n-2);  // 递归分解为两个子问题
}

代码解析：

  1. 递归终止条件：当n<=1时直接返回n值
  2. 递归关系：F(n) = F(n-1) + F(n-2)
  3. 问题分析：计算F(5)需要计算F(4)和F(3)，而计算F(4)又需要F(3)和F(2)，存在大量重复计算
  4. 时间复杂度：二叉树结构，O(2^n)，空间复杂度O(n)（调用栈深度）

1.2 记忆化递归实现解析

int memo[100] = {0};  // 全局记忆数组，默认初始化为0

int fib_memo(int n) {
    if(n <= 1) return n;
    if(memo[n] != 0)  // 检查是否已计算过
        return memo[n];
    return memo[n] = fib_memo(n-1) + fib_memo(n-2);  // 计算结果并存储
}

代码解析：

  1. memo数组存储已计算结果，初始值为0表示未计算
  2. 每次递归调用前检查是否已有缓存结果
  3. 通过空间换时间，将重复计算转化为查表操作
  4. 时间复杂度优化到O(n)，空间复杂度O(n)

1.3 迭代法实现解析

int fib_tab(int n) {
    if(n == 0) return 0;
    int dp[n+1];          // 创建DP表
    dp[0] = 0;            // 初始化基础条件
    dp[1] = 1;
    for(int i=2; i<=n; ++i)
        dp[i] = dp[i-1] + dp[i-2];  // 递推填充表格
    return dp[n];
}

代码解析：

  1. dp数组索引对应斐波那契数列的位置
  2. 初始化前两个已知值
  3. 循环从2开始逐步构建后续结果
  4. 时间复杂度O(n)，空间复杂度O(n)（可优化为O(1)）

二、经典问题深度解析

2.1 最长公共子序列（LCS）完整解析

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

int lcs(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    // 创建(m+1)x(n+1)的二维DP表，+1是为了处理空字符串的情况
    vector<vector<int>> dp(m+1, vector<int>(n+1, 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] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}

代码解析：

  1. 状态定义：dp[i][j]表示text1前i个字符与text2前j个字符的LCS长度
  2. 初始化：第一行和第一列初始为0，表示空字符串的情况
  3. 状态转移：
    • 当字符匹配时：LCS长度+1，继承左上方值+1
    • 当字符不匹配时：取上方或左方的最大值
  4. 遍历顺序：双重循环按行填充表格
  5. 示例分析：
    text1 = “abcde”, text2 = “ace”
    DP表最终值为3（LCS为"ace"）

2.2 0-1背包问题完整解析

问题描述：给定物品重量数组wt和价值数组val，背包容量W，求能装的最大价值

int knapsack(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.size();
    vector<int> dp(W+1, 0);  // 一维DP数组优化空间

    for(int i=0; i<n; ++i) {            // 遍历每个物品
        for(int w=W; w>=wt[i]; --w) {   // 逆序更新防止覆盖
            dp[w] = max(dp[w],                    // 不选当前物品
                       dp[w - wt[i]] + val[i]);  // 选择当前物品
        }
    }
    return dp[W];
}

代码解析：

  1. 状态定义：dp[w]表示容量为w时的最大价值
  2. 空间优化：使用一维数组替代二维数组
  3. 逆序遍历原因：保证每个物品只被考虑一次，避免重复使用
  4. 状态转移方程分析：
    • 不选物品i：价值保持dp[w]不变
    • 选物品i：价值为dp[w-wt[i]] + val[i]
  5. 示例分析：
    W=4, wt=[2,3,4], val=[3,4,5]
    最终dp[4] = max(不选4: dp[4], 选4: dp[0]+5) = 5

2.3 编辑距离完整解析

问题描述：计算将word1转换成word2所需的最小操作次数（插入、删除、替换）

int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

    // 初始化边界条件
    for(int i=0; i<=m; ++i) dp[i][0] = i;  // 删除i次
    for(int j=0; j<=n; ++j) dp[0][j] = j;  // 插入j次

    for(int i=1; i<=m; ++i) {
        for(int j=1; j<=n; ++j) {
            if(word1[i-1] == word2[j-1]) {  // 字符相同无需操作
                dp[i][j] = dp[i-1][j-1];
            } else {  // 选择三种操作中的最小代价
                dp[i][j] = 1 + min({dp[i-1][j],   // 删除word1字符
                                  dp[i][j-1],   // 插入word2字符
                                  dp[i-1][j-1]});// 替换字符
            }
        }
    }
    return dp[m][n];
}

代码解析：

  1. 状态定义：dp[i][j]表示转换前i个字符到前j个字符的最小操作数
  2. 边界初始化：
    • 第一列表示将word1删成空串的操作次数
    • 第一行表示将空串插入成word2的操作次数
  3. 状态转移分析：
    • 字符匹配：直接继承左上方值
    • 字符不匹配：取三种操作的最小值+1
  4. 操作类型对应关系：
    • 删除：相当于处理word1的前i-1个字符
    • 插入：相当于处理word2的前j-1个字符
    • 替换：相当于处理i-1和j-1的情况后修改字符
  5. 示例分析：
    word1 = “horse”, word2 = “ros”
    最终编辑距离为3（替换h→r，删除 r，删除 e）

三、动态规划优化技巧详解

3.1 斐波那契数列空间优化

int fib_opt(int n) {
    if(n == 0) return 0;
    int prev = 0, curr = 1;  // 初始值F(0)=0, F(1)=1
    for(int i=2; i<=n; ++i) {
        int next = prev + curr;  // 计算下一个值
        prev = curr;  // 更新前一个值
        curr = next;  // 更新当前值
    }
    return curr;
}

优化原理：

  1. 观察发现每个状态只依赖前两个状态
  2. 使用两个变量代替数组存储历史值
  3. 空间复杂度从O(n)降到O(1)
  4. 滚动更新机制：
    • 每次迭代将prev更新为前一个curr
    • curr更新为新的计算结果

3.2 背包问题空间优化

// 二维原始版本
int dp[n+1][W+1]; 

// 优化为一维数组
vector<int> dp(W+1, 0);

优化原理：

  1. 二维数组中每一行只依赖上一行的数据
  2. 逆序更新避免覆盖未使用的旧值
  3. 关键点：内层循环必须从W到wt[i]逆序进行
  4. 示例说明：
    • 正序更新会导致物品被重复选取（完全背包问题）
    • 逆序更新保证每个物品只被考虑一次

四、动态规划解题方法论

4.1 状态定义技巧

  1. 确定问题变量维度：

    • 单序列问题（如LIS）：一维状态dp[i]
    • 双序列问题（如LCS）：二维状态dp[i][j]
    • 带约束问题（如背包）：二维状态dp[i][w]

  2. 常见状态定义模式：

    • “前i个元素…”：如dp[i]表示前i个元素的最优解
    • “以第i个元素结尾…”：如最长递增子序列问题
    • “位置(i,j)…”：如矩阵路径问题

4.2 状态转移方程建立

  1. 分析子问题关系：

    • 如何从较小规模的子问题推导当前问题
    • 举例：在编辑距离中，三种操作对应三种子问题转移路径

  2. 方程建立步骤：
    (1) 列出所有可能的决策选项
    (2) 计算每个决策对应的子问题解
    (3) 选择最优决策并组合结果

4.3 初始化技巧

  1. 边界条件处理：

    • 空字符串/空集合的处理
    • 初始值的物理意义（如背包容量为0时价值为0）

  2. 特殊值初始化示例：

    // 矩阵路径问题初始化第一行和第一列
for(int i=0; i<m; ++i) dp[i][0] = 1;
for(int j=0; j<n; ++j) dp[0][j] = 1;

五、综合案例分析

5.1 最大子数组和

问题描述：求整数数组中和最大的连续子数组

int maxSubArray(vector<int>& nums) {
    int currMax = nums[0], globalMax = nums[0];
    for(int i=1; i<nums.size(); ++i) {
        // 决策：继续扩展子数组 or 重新开始
        currMax = max(nums[i], currMax + nums[i]);
        // 更新全局最大值
        globalMax = max(globalMax, currMax);
    }
    return globalMax;
}

算法解析：

  1. 状态定义：currMax表示以当前元素结尾的最大子数组和
  2. 状态转移方程：
    currMax = max(nums[i], currMax + nums[i])
  3. 空间优化：仅需维护两个变量
  4. 示例分析：
    输入：[-2,1,-3,4,-1,2,1,-5,4]
    输出：6（子数组[4,-1,2,1]）

5.2 不同路径问题

问题描述：m x n网格从左上角到右下角的唯一路径数

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for(int i=1; i<m; ++i) {
        for(int j=1; j<n; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

算法解析：

  1. 状态定义：dp[i][j]表示到达(i,j)的路径数
  2. 状态转移方程：dp[i][j] = 上方路径数 + 左方路径数
  3. 初始化技巧：第一行和第一列都只有1种路径
  4. 空间优化：可用一维数组替代，dp[j] += dp[j-1]

六、动态规划调试技巧

6.1 DP表可视化

  1. 打印DP表中间状态
    // 在LCS代码中插入调试输出
for(auto& row : dp) {
    for(int val : row) cout << val << " ";
    cout << endl;
}
  2. 观察表数据是否符合预期

6.2 边界测试用例

  1. 空输入测试：空字符串、空数组等
  2. 极值测试：n=0, W=0等特殊情况
  3. 示例测试：使用题目给出的示例验证

6.3 常见错误排查

  1. 数组越界：检查索引是否正确（特别是从1开始的情况）
  2. 初始化错误：验证边界条件是否正确设置
  3. 循环顺序错误：检查是否按正确依赖顺序填充表格
  4. 状态转移方程错误：用简单用例手动验证

七、动态规划复杂度分析指南

7.1 时间复杂度计算

  1. 基本公式：状态数 × 每个状态的转移成本

    • LCS问题：O(mn)状态 × O(1)转移 = O(mn)
    • 背包问题：O(nW)状态 × O(1)转移 = O(nW)

  2. 多项式时间与伪多项式时间：

    • 背包问题的O(nW)称为伪多项式时间
    • 当W很大时（如指数级），算法效率会显著下降

7.2 空间复杂度优化

  1. 滚动数组技巧：

    • 二维→一维：当当前行只依赖前一行时
    • 示例：斐波那契数列、背包问题

  2. 状态压缩技巧：

    • 使用位运算表示状态集合
    • 常见于旅行商问题（TSP）等状压DP

八、动态规划进阶路线图

8.1 学习路径建议

  1. 基础阶段（1-2周）：

    • 斐波那契数列
    • 爬楼梯问题
    • 最大子数组和

  2. 提高阶段（2-4周）：

    • 背包问题系列
    • 字符串编辑问题
    • 矩阵路径问题

  3. 精通阶段（1-2月）：

    • 树形DP（二叉树最大路径和）
    • 状态压缩DP（TSP问题）
    • 区间DP（矩阵链乘法）

8.2 推荐练习题目

题目类型 LeetCode题号 难度
爬楼梯 70 简单
最长递增子序列 300 中等
零钱兑换 322 中等
正则表达式匹配 10 困难
买卖股票最佳时机 121/123 中等

九、动态规划代码模板库

9.1 一维DP模板

int dp[n]; 
dp[0] = initial_value;

for(int i=1; i<n; ++i) {
    dp[i] = compute(dp[...]);
}

return dp[n-1];

9.2 二维DP模板

vector<vector<int>> dp(m, vector<int>(n, 0));

// 初始化边界
for(int i=0; i<m; ++i) dp[i][0] = ...;
for(int j=0; j<n; ++j) dp[0][j] = ...;

// 填充表格
for(int i=1; i<m; ++i) {
    for(int j=1; j<n; ++j) {
        dp[i][j] = compute(dp[i-1][j], dp[i][j-1], ...);
    }
}

十、动态规划常见问题FAQ

Q：如何判断一个问题是否可以用DP解决？
A：检查问题是否具有：

  1. 最优子结构性质
  2. 重叠子问题性质
  3. 无后效性（当前决策不影响之前状态）

Q：DP和分治法的区别是什么？
A：分治法将问题分解为独立的子问题，而DP处理的是重叠的子问题

Q：如何处理环形结构问题？
A：常用技巧：

  1. 破环成链（复制数组）
  2. 分类讨论（考虑包含首元素和不包含的情况）

Q：如何选择记忆化递归还是迭代法？
A：

  • 记忆化递归更直观，适合树形结构问题
  • 迭代法效率更高，适合需要空间优化的情况
  • 动态规划导图
    在这里插入图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布