C++ 动态规划算法基础

小布老师2025-02-042025-11-26

C++ 动态规划算法基础

前言

动态规划（Dynamic Programming，简称DP）是算法设计中的一种重要方法，广泛应用于解决最优化问题。本文将介绍动态规划的基本概念、核心思想，以及两种常用的分析方法：常规分析方法和闫氏DP分析法。

本文导航：

📚 动态规划基础：定义、核心思想、基本要素
🔄 解题步骤：五步法解决DP问题
📖 常规分析方法：传统DP分析方法
🎯 闫氏DP分析法：集合角度的系统化方法
⚖️ 两种方法对比：选择适合的分析方法
📦 常见DP类型：线性、区间、背包、树形、状态压缩
🚀 优化技巧：空间优化、状态优化、转移优化
💡 学习建议：如何学好动态规划

一、什么是动态规划

1. 动态规划的定义

动态规划是一种通过把原问题分解为相对简单的子问题的方式来解决复杂问题的方法。它通常用于解决具有重叠子问题和最优子结构性质的问题。

动态规划的核心思想是：

记忆化：避免重复计算已经求解过的子问题
自底向上：从最小的子问题开始，逐步构建更大问题的解
状态转移：通过状态转移方程描述问题之间的关系

2. 动态规划与贪心、分治的区别

动态规划、贪心算法和分治算法是三种重要的算法设计方法，它们各有特点：

方法	特点	适用场景
贪心算法	每一步都做出当前最优选择，不考虑全局	局部最优能导致全局最优的问题
分治算法	将问题分解为独立的子问题，递归求解	子问题之间相互独立的问题
动态规划	将问题分解为重叠的子问题，记忆化求解	具有重叠子问题和最优子结构的问题

3. 动态规划的基本要素

最优子结构

问题的最优解包含子问题的最优解。也就是说，可以通过子问题的最优解来构造原问题的最优解。

示例：在最短路径问题中，如果从A到C的最短路径经过B，那么从A到B和从B到C的路径也分别是最短的。

重叠子问题

在递归求解过程中，同一个子问题会被多次计算。

示例：在计算斐波那契数列时，fib(5) 需要计算 fib(4) 和 fib(3)，而 fib(4) 又需要计算 fib(3) 和 fib(2)，fib(3) 被重复计算了。

状态转移方程

描述问题状态之间关系的数学表达式，是动态规划的核心。

示例：斐波那契数列的状态转移方程为：f(n) = f(n-1) + f(n-2)

二、动态规划的解题步骤

常规解题步骤

确定状态：定义问题的状态，通常用 dp[i] 或 dp[i][j] 表示
确定状态转移方程：找出状态之间的关系
确定初始状态：设置边界条件
确定计算顺序：确定状态的计算顺序（自底向上或自顶向下）
编写代码：根据上述分析编写代码

三、动态规划分析方法

方法一：常规分析方法

常规分析方法是最常用的动态规划分析方法，通过以下步骤进行：

1. 问题分析

理解问题：明确问题的目标和约束条件
识别特征：判断是否具有最优子结构和重叠子问题
确定状态：定义状态变量，表示问题的子问题

2. 状态定义

状态定义是动态规划的基础，需要明确：

状态的含义：dp[i] 或 dp[i][j] 表示什么
状态的维度：一维、二维还是多维
状态的取值范围：状态的取值范围

示例：在01背包问题中，可以定义 dp[i][j] 表示前i个物品在容量为j的背包中能获得的最大价值。

3. 状态转移方程

状态转移方程描述了状态之间的关系，通常有以下几种形式：

线性DP：dp[i] = f(dp[i-1], dp[i-2], ...)
区间DP：dp[i][j] = f(dp[i][k], dp[k+1][j])
树形DP：在树上进行状态转移
背包DP：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

4. 初始状态

初始状态是状态转移的起点，需要明确：

边界条件：最小子问题的解
初始值：dp[0] 或 dp[0][0] 的值

5. 计算顺序

确定状态的计算顺序，确保在计算 dp[i] 时，所需的子问题已经计算完成。

示例：在01背包问题中，通常从 i=1, j=0 开始，逐步计算到 i=n, j=V。

6. 完整示例：斐波那契数列

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

分析过程：

状态定义：dp[i] 表示第i个斐波那契数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
初始状态：dp[0] = 0, dp[1] = 1
计算顺序：从 i=2 开始，依次计算到 i=n

代码实现：

#include <iostream>
#include <vector>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) return n;
    
    // 【状态定义】dp[i] 表示第i个斐波那契数
    vector<int> dp(n + 1);
    
    // 【初始状态】
    dp[0] = 0;
    dp[1] = 1;
    
    // 【状态转移】从i=2开始计算
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];  // 状态转移方程
    }
    
    return dp[n];
}

// 【空间优化版本】只保留前两个状态
int fibonacci_optimized(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0;  // dp[i-2]
    int prev1 = 1;  // dp[i-1]
    
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;  // dp[i] = dp[i-1] + dp[i-2]
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}

int main() {
    int n = 10;
    cout << "第" << n << "个斐波那契数: " << fibonacci(n) << endl;
    cout << "优化版本: " << fibonacci_optimized(n) << endl;
    return 0;
}

代码说明：

基础版本使用一维数组存储所有状态，空间复杂度为 O(n)
优化版本只保留前两个状态，空间复杂度优化为 O(1)
两种方法的时间复杂度都是 O(n)

方法二：闫氏DP分析法

闫氏DP分析法是由算法竞赛教练闫学灿（yxc）总结的一种系统化的动态规划分析方法。这种方法通过集合的角度来理解动态规划，使问题分析更加清晰和系统化。

闫氏DP分析法的核心思想

闫氏DP分析法将动态规划问题看作集合划分问题：

状态表示：用集合来表示状态
- dp[i] 或 dp[i][j] 表示一个集合
- 集合中存储的是所有满足某种条件的方案
- 集合的属性（最大值、最小值、数量等）就是我们要计算的值
状态计算：通过集合划分来计算状态
- 将当前集合划分为若干个子集
- 每个子集对应一种情况
- 通过子集的结果来计算当前集合的属性

闫氏DP分析法的步骤

闫氏DP分析法分为两个核心步骤：

第一步：状态表示

集合：dp[i][j] 表示什么集合？
属性：集合的属性是什么？（最大值、最小值、数量等）

第二步：状态计算

集合划分：如何将当前集合划分为子集？
状态转移：如何通过子集的结果计算当前集合的属性？

完整示例：01背包问题（闫氏DP分析法）

问题描述：有N个物品和一个容量为V的背包。每个物品只能使用一次。第i个物品的体积是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量，且总价值最大。

闫氏DP分析：

第一步：状态表示

集合：dp[i][j] 表示所有只考虑前i个物品，且总体积不超过j的选法集合
属性：集合中所有方案的最大价值

第二步：状态计算

将集合 dp[i][j] 划分为两个子集：

不选第i个物品：只考虑前i-1个物品，总体积不超过j
- 对应集合：dp[i-1][j]
- 价值：dp[i-1][j]
选第i个物品：只考虑前i-1个物品，总体积不超过 j-w[i]，然后加上第i个物品
- 对应集合：dp[i-1][j-w[i]]
- 价值：dp[i-1][j-w[i]] + v[i]

状态转移方程：

1	dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

边界条件：

dp[0][j] = 0（没有物品，价值为0）
dp[i][0] = 0（容量为0，价值为0）

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int knapsack01(int n, int V, vector<int>& w, vector<int>& v) {
    // 【状态定义】dp[i][j] 表示前i个物品，容量为j时的最大价值
    vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));
    
    // 【状态转移】
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            // 不选第i个物品
            dp[i][j] = dp[i-1][j];
            
            // 选第i个物品（需要容量足够）
            if (j >= w[i-1]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }
    
    return dp[n][V];
}

// 【空间优化版本】使用一维数组
int knapsack01_optimized(int n, int V, vector<int>& w, vector<int>& v) {
    vector<int> dp(V + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // 【注意】需要逆序遍历，避免覆盖未使用的状态
        for (int j = V; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }
    
    return dp[V];
}

int main() {
    int n = 4, V = 5;
    vector<int> w = {1, 2, 3, 4};  // 重量
    vector<int> v = {2, 4, 4, 5};  // 价值
    
    cout << "最大价值: " << knapsack01(n, V, w, v) << endl;
    cout << "优化版本: " << knapsack01_optimized(n, V, w, v) << endl;
    return 0;
}

代码说明：

基础版本使用二维数组，空间复杂度为 O(n×V)
优化版本使用一维数组，空间复杂度优化为 O(V)
关键点：一维优化时需要逆序遍历容量，避免覆盖未使用的状态
两种方法的时间复杂度都是 O(n×V)

闫氏DP分析法的优势

系统化：通过集合的角度统一理解各种DP问题
清晰性：集合划分使状态转移更加清晰
通用性：适用于各种类型的动态规划问题
易于理解：从集合的角度更容易理解状态的含义

四、两种方法的对比

以下是常规分析方法和闫氏DP分析法的详细对比：

方面	常规分析方法	闫氏DP分析法
核心思想	通过状态转移方程描述问题	通过集合划分理解问题
分析角度	状态之间的关系	集合的属性和划分
适用场景	所有DP问题	所有DP问题
理解难度	中等	相对容易（系统化）
优势	直观，易于上手	系统化，逻辑清晰