052. 理解动态规划的基本概念

动态规划（Dynamic Programming，简称DP）是一种解决复杂问题的算法思想，它通过将问题分解为更小的子问题，并将子问题的解存储起来（通常使用表格或数组），避免重复计算，从而提高算法的效率。动态规划特别适用于具有重叠子问题和最优子结构的问题。

1. 动态规划的基本概念

1.1 最优子结构

如果一个问题的最优解包含其子问题的最优解，则称该问题具有最优子结构。这意味着可以通过求解子问题的最优解来构建原问题的最优解。

1.2 重叠子问题

在递归求解过程中，如果某些子问题被多次重复计算，则称该问题具有重叠子问题。动态规划通过存储这些子问题的解，避免了重复计算，从而提高了效率。

1.3 状态和状态转移方程

状态：动态规划中的状态通常是一个变量或一组变量，用于描述问题的某个阶段的状态。状态的选择需要满足无后效性，即当前状态的决策只依赖于当前状态，而不依赖于之前的状态。
状态转移方程：描述状态之间的关系，即如何从一个状态转移到另一个状态。状态转移方程是动态规划的核心，它决定了如何通过子问题的解来构建原问题的解。

2. 动态规划的实现步骤

定义状态：确定问题的每个阶段的状态，选择合适的状态变量。
建立状态转移方程：根据问题的性质，推导出状态之间的关系。
初始化边界条件：确定动态规划的初始状态，即边界条件。
确定计算顺序：根据状态转移方程，确定计算的顺序（通常是自底向上）。
存储中间结果：使用数组或表格存储中间结果，避免重复计算。

3. 动态规划的典型应用

示例1：斐波那契数列

斐波那契数列是一个经典的动态规划问题。斐波那契数列的定义如下： F(n)=F(n−1)+F(n−2) 其中，F(0)=0，F(1)=1。

递归实现（效率低，存在大量重复计算）：

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

动态规划实现（效率高，避免重复计算）：

int fibonacci(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];
}

示例2：背包问题

背包问题是一个经典的动态规划问题。给定一组物品，每个物品有重量和价值，确定在不超过背包容量的情况下，选择哪些物品可以使总价值最大。

状态定义：

dp[i][j] 表示前 i 个物品在背包容量为 j 时的最大价值。

状态转移方程：

如果不选择第 i 个物品：dp[i][j] = dp[i-1][j]
如果选择第 i 个物品：dp[i][j] = dp[i-1][j - weight[i]] + value[i]（前提是 j >= weight[i]）

代码实现：

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack(int W, int weights[], int values[], int n) {
    int dp[n + 1][W + 1];

    // 初始化
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = 0;
        }
    }

    // 动态规划填表
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (w >= weights[i - 1]) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int weights[] = {10, 20, 30};
    int values[] = {60, 100, 120};
    int W = 50;
    int n = sizeof(values) / sizeof(values[0]);

    printf("最大价值：%d\n", knapsack(W, weights, values, n));
    return 0;
}

4. 动态规划的特点

高效性：动态规划通过存储子问题的解，避免了重复计算，显著提高了算法的效率。
适用性：动态规划适用于具有最优子结构和重叠子问题的问题，如背包问题、最长公共子序列、最短路径问题等。
空间复杂度：动态规划通常需要额外的空间来存储中间结果，空间复杂度取决于状态的数量。可以通过优化（如滚动数组）减少空间复杂度。
状态转移方程：动态规划的核心是状态转移方程，正确推导状态转移方程是解决问题的关键。

5. 总结

动态规划是一种强大的算法思想，通过将问题分解为更小的子问题，并存储子问题的解，避免重复计算，从而高效地解决复杂问题。理解动态规划的关键在于掌握最优子结构、重叠子问题和状态转移方程。通过多练习和总结，可以更好地掌握动态规划的应用。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)