DP-动态规划详解

DP算法简介

DP算法即动态规划 (Dynamic Programming) 算法，是一种解决复杂问题的有效方法，它将问题分解为相互重叠的子问题，并通过存储子问题的解来避免重复计算，从而提高效率。

核心思想

动态规划基于两个关键思想：

1. 最优子结构：问题的最优解包含其子问题的最优解
2. 重叠子问题：在递归求解过程中，相同的子问题会被多次计算

基本步骤

1. 定义状态：找出问题的状态表示方式
2. 建立状态转移方程：确定状态之间的关系
3. 确定初始条件和边界条件
4. 计算顺序：通常采用自底向上或记忆化搜索的方式
5. 构造最终解

例题

背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v[i]，价值是 w[i]。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v[i]，w[i]，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N, V ≤ 1000
0 < v[i], w[i] ≤ 1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8

代码

第一步：用 dfs 暴力枚举

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];

// x 表示当前的第x个物品，spV 表示背包剩余容量。
int dfs(int x, int spV) {
    // 如果物品的编号超过了总数，返回 0，这样在后续 max 函数中必然不会选到这个超出的物品。
    // 这里是在处理边界情况，因为选到最后一个物品的时候他也会判断还要不要选下一个物品。
    if (x > n) {
        return 0;
    }
    
    if (v[x] > spV) { // 如果背包容量不够。
        // 不选当前物品，去判断下一个物品。
        return dfs(x + 1, spV);
    } else { // 如果背包空间足够。
        // 判断选这个物品和不选这个物品的总价值哪个大，返回那个结果。
        return max(dfs(x + 1, spV), dfs(x + 1, spV - v[x]) + w[x]);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &v[i], &w[i]);
    }
    
    // 从第一个物品开始判断，此时背包剩余容量为总容量。
    int res = dfs(1, m);
    
    printf("%d\n", res);
    return 0;
}

• 很显然，这个算法会超时，因为重复计算了很多节点。
• 很自然的想到，如果把已经算过的节点存下来，需要的时候直接返回其值，就可以大幅节省时间。

第二步：记忆化搜索

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
// 定义 mem 数组，dfs 函数是二维，因此这个数组也是二维。
int mem[N][N];

// x 表示当前的第x个物品，spV 表示背包剩余容量。
int dfs(int x, int spV) {
    // 最关键的一步优化，如果已经算过，直接返回。
    if (mem[x][spV]) return mem[x][spV];

    // 用于计算总价值。
    int sum;

    // 超过的部分因为不存在，所以价值为0，但避免函数继续运行下去，不用 sum = 0，而是直接 return。
    if (x > n) {
         return 0;
    }
    
    if (v[x] > spV) { // 如果背包容量不够。
        // 不选当前物品，去判断下一个物品。
        sum = dfs(x + 1, spV);
    } else { // 如果背包空间足够。
        // 判断选这个物品和不选这个物品的总价值哪个大，返回那个结果。
        sum = max(dfs(x + 1, spV), dfs(x + 1, spV - v[x]) + w[x]);
    }

    // 存储
    mem[x][spV] = sum;
    return sum;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &v[i], &w[i]);
    }
    
    // 从第一个物品开始判断，此时背包剩余容量为总容量。
    int res = dfs(1, m);
    
    printf("%d\n", res);
    return 0;
}

• 时间复杂度成功从 O(2^n) 降到了 O(nm)，但是空间复杂度从 O(n) 提高到了 O(nm) 典型的以空间换时间算法。
• 这样的写法已经做到了优化（其实一般情况下到这一步就可以了），但是这样的写法不够优雅，而且打字也多（如果你就喜欢多敲代码当我没说）。
• 下一个方法是通过递推写出 状态转移方程，你会发现这和 dfs 的每一步是对应的。

第三步：递推实现

为了体现一一对应，我就不把 dfs 函数删掉了

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int mem[N][N];
// 该数组用于存储 某一物品 在 某一背包容量的情况下 开始决策的最优解
int f[N][N];

int dfs(int x, int spV) {
    if (mem[x][spV]) return mem[x][spV];
    
    int sum;

    if (x > n) {
        return 0;
    }
    
    if (v[x] > spV) {
        sum = dfs(x + 1, spV);
    } else {
        sum =  max(dfs(x + 1, spV), dfs(x + 1, spV - v[x]) + w[x]);
    }
    
    mem[x][spV]= sum;
    return sum;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &v[i], &w[i]);
    }
    
    // 枚举出所有物品在不同剩余容量的情况下的最优解。
    // 从下往上枚举物品。
    for (int i = n; i >= 1; i--) {
        // 从 0 开始遍历背包容量。
        for (int j = 0; j <= m; j++) {
            if (j < v[i]) { // 如果背包不够装。
                // 去判断下一个物品在当前背包容量够不够。
                f[i][j] = f[i + 1][j];
            } else { // 如果够装。
                // 两种选择：选或不选当前物品，得出最优解。
                f[i][j] = max(f[i + 1][j], f[i + 1][j - v[i]] + w[i]);
            }
        }
    }
    
    // 因为物品编号从下往上递推，容量从 0 到 m 遍历。
    // 而答案就是第 1 个物品在背包容量为 m 的情况下开始决策的最优解。
    printf("%d\n", f[1][m]);
    return 0;
}

• 这里可以更加直观的看出时空复杂度，很显然和 dfs + 记忆化搜索 是一样的。
• 还有没有更优解呢？

第四步：进一步优化

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];  // 一维数组

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &v[i], &w[i]);
    }
    
    for (int i = n; i >= 1; i--) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    printf("%d\n", f[m]);
    return 0;
}

关键点说明：

1. 我们只需要一个一维数组 f[N]，而不是二维数组 f[N][N]。
2. 内层循环需要从大到小遍历（从 m 到 v[i]），这样可以确保在计算 f[j] 时，f[j - v[i]] 还是上一轮 i+1 的值。
3. 当 j < v[i] 时，f[j] 保持不变，所以不需要处理。

经过这一次优化，空间复杂度就变为了 O(n)，但是一般情况下这一步优化都是不必要的。

总结

DP算法依赖你对 dfs 和状态转移方程的理解，现在你发现他们是一回事了。
有的人可能会有疑问，为什么不用贪心？
因为贪心是寻找局部最优解，而 DP是寻找全局最优解，如果每次能取物品的一部分而没有要求一定要取走整个物品，用的就是贪心了。