深入理解动态规划：从入门到精通

深入理解动态规划：从入门到精通

引用

CSDN

1.

https://blog.csdn.net/2302_77582029/article/details/146291539

动态规划（Dynamic Programming, DP）是解决复杂问题的一种高效方法。它通过将问题分解为子问题，并保存子问题的解，避免重复计算，从而提高效率。本文将详细介绍动态规划的基本思想、实现方法、优化技巧以及典型应用场景，帮助读者从入门到精通动态规划。

动态规划的基本思想

定义

动态规划是一种通过将问题分解为子问题，并保存子问题的解，避免重复计算的算法设计方法。

适用条件

• 最优子结构：问题的最优解包含子问题的最优解。
• 重叠子问题：子问题之间存在重叠，可以复用解。

示例

以斐波那契数列为例：

• 问题：计算第n个斐波那契数。
• 子问题：计算第(n-1)和第(n-2)个斐波那契数。
• 重叠子问题：计算第(n-1)个数时需要计算第(n-2)个数。

动态规划的实现

以下是动态规划的经典问题——斐波那契数列的C++实现代码。

代码实现

#include <iostream>
#include <vector>
using namespace std;
int fibonacci(int n) {
    if (n <= 1) return n;
    vector<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];
}
int main() {
    int n = 10;
    cout << "斐波那契数列第 " << n << " 项: " << fibonacci(n) << endl;
    return 0;
}

代码解析

• 状态定义：dp[i]表示第i个斐波那契数。
• 状态转移方程：dp[i] = dp[i - 1] + dp[i - 2]。
• 初始化：dp[0] = 0，dp[1] = 1。
• 空间优化：可以使用两个变量代替数组，减少空间复杂度。

动态规划的典型应用

背包问题

• 0-1背包问题：每个物品只能选择一次。
• 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。
• 完全背包问题：每个物品可以选择多次。
• 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])。

最长公共子序列（LCS）

• 问题：求两个序列的最长公共子序列。
• 状态转移方程：
• 如果s1[i-1] == s2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1。
• 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最短路径问题

• Floyd-Warshall算法：求所有节点对之间的最短路径。
• 状态转移方程：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])。

编辑距离

• 问题：求将一个字符串转换为另一个字符串的最小操作次数。
• 状态转移方程：
• 如果s1[i-1] == s2[j-1]，则dp[i][j] = dp[i-1][j-1]。
• 否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

动态规划的优化

空间优化

• 使用滚动数组或变量代替二维数组，减少空间复杂度。
• 示例：斐波那契数列的空间优化。

int fibonacci(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; ++i) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

状态压缩

• 使用位运算或其他技巧压缩状态表示，减少空间复杂度。
• 示例：旅行商问题（TSP）的状态压缩。

记忆化搜索

• 使用递归和记忆化技术实现动态规划，避免显式定义状态转移方程。
• 示例：斐波那契数列的记忆化搜索。

int fib(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

动态规划的总结

动态规划是一种强大的算法设计方法，适用于具有最优子结构和重叠子问题的问题。通过理解其原理、实现方法和优化技巧，我们可以更好地应用它解决实际问题。无论是背包问题、最长公共子序列还是最短路径问题，动态规划都发挥着重要作用。