当前位置：首页 > article >正文

初识动态规划(由浅入深)

article 2024/11/4 21:55:00

🤓 动态规划入门与进阶指南 📘

动态规划（Dynamic Programming, DP）是一种非常经典的📐算法方法，特别适合用来解决那些有大量重复计算的问题🌀。它可以将复杂的问题拆分为小问题🧩，然后一步一步地找到最终答案🎯。本文将介绍动态规划的基本概念💡，讲解它的好处👍，并通过一些例子展示动态规划的用法，还会与简单的暴力求解方法进行对比⚖️。最后，我们会讨论一些更复杂的例子，帮助你更好地理解动态规划。

❓ 什么是动态规划？

动态规划是一种把问题分成更小的子问题🔍，并用这些子问题的答案来解决整个问题的方法。动态规划最常用于具有 重叠子问题♻️ 和 最优子结构⭐ 的问题。

重叠子问题♻️：一个大问题可以被分成多个小问题🧩，而且这些小问题会被多次求解。
最优子结构⭐：问题的最优解可以通过其子问题的最优解来构造🛠️。

通过记住每个子问题的答案📝，动态规划可以避免重复计算，显著提高效率⏱️。

在应用动态规划时，我们通常会使用一个状态数组📊来表示每个小问题的解，然后使用状态转移方程来描述如何从这些子问题得到最终答案🏁。动态规划的核心思想是利用之前已经计算出的结果来避免重复工作。

📊 经典实例对比

1️⃣ 斐波那契数列

🔢 问题描述

斐波那契数列的定义是：

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2)，当 n >= 2

目标是计算斐波那契数列的第 n 项📍。

💥 暴力递归求解

// 递归暴力求解
// 时间复杂度：O(2^n)
public static int fibonacciRecursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

这种暴力方法简单直接🌀，但它的时间复杂度是 O(2^n)，因为它会重复计算很多相同的子问题🔄。对于较大的 n 值，这种方法效率非常低⚠️。

🚀 动态规划求解

我们可以使用动态规划，通过记忆化或从底向上的方式来避免重复计算：

// 动态规划求解（自底向上）
// 时间复杂度：O(n)，空间复杂度：O(n)
public static int fibonacciDP(int n) {
    if (n <= 1) {
        return n;
    }
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

使用动态规划，我们可以将时间复杂度降低到 O(n)，并且通过记忆中间结果来减少重复计算🗂️。虽然空间复杂度是 O(n)，但这个方法能显著减少计算时间⏳。

🛠️ 优化后的动态规划解法

我们可以进一步优化空间复杂度，只存储最近的两个值：

// 优化后的动态规划求解
// 时间复杂度：O(n)，空间复杂度：O(1)
public static int fibonacciOptimized(int n) {
    if (n <= 1) {
        return n;
    }
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

在这个实现中，我们将空间复杂度降低到了 O(1)。这种方法的核心是每次只保留最近的两个斐波那契数，因此大大节省了内存💾。

2️⃣ 0/1 背包问题 🎒

❓ 问题描述

有 n 个物品，每个物品有一定的重量和价值⚖️💰，背包的最大容量是 W。目标是在不超过容量的情况下，使背包内的物品总价值最大化💵。

重量数组：weights = [2, 3, 4, 5]
价值数组：values = [3, 4, 5, 6]
背包容量：W = 5

💥 暴力求解

暴力求解就是穷举所有可能的组合🔢，找到最大价值💰。时间复杂度为 O(2^n)，因为每个物品都有 “选择” 或 “不选择” 两种可能。这种方法在物品数量多时非常低效⚠️。

🚀 动态规划求解

我们可以用动态规划，通过创建一个二维数组📊来存储子问题的解。状态转移方程为：

dp[i][w] 表示前 i 个物品在容量为 w 时的最大价值。
转移方程为：
- 如果不选第 i 个物品：dp[i][w] = dp[i-1][w]
- 如果选第 i 个物品：dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])

// 动态规划求解 0/1 背包问题
// 时间复杂度：O(n * W)，空间复杂度：O(n * W)
public static int knapsack(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.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];
}

时间和空间复杂度都是 O(n * W)。动态规划避免了重复计算，从而显著提高了求解效率⏳。

🛠️ 优化空间复杂度

我们可以将二维数组优化为一维数组，只需记录前一行的数据：

// 优化后的动态规划求解 0/1 背包问题
// 时间复杂度：O(n * W)，空间复杂度：O(W)
public static int knapsackOptimized(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[] dp = new int[W + 1];
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

通过使用一维数组，空间复杂度可以降低到 O(W)，这使得动态规划在处理大规模的背包问题时更有效🔋。
至于为什么要反向遍历呢？

3️⃣ 编辑距离问题 ✍️

❓ 问题描述

编辑距离是指把一个字符串转换为另一个字符串所需的最少操作次数🔄。允许的操作包括插入、删除和替换字符。比如，把 “kitten” 变成 “sitting” 需要 3 次操作。

🚀 动态规划求解

我们可以使用动态规划来解决这个问题。dp[i][j] 表示把 word1[0:i] 变成 word2[0:j] 需要的最小操作次数🔢。

状态转移方程为：

如果 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]
否则，dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)

// 编辑距离的动态规划解法
// 时间复杂度：O(m * n)，空间复杂度：O(m * n)
public static int editDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0) {
                dp[i][j] = j;
            } else if (j == 0) {
                dp[i][j] = i;
            } else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
            }
        }
    }
    return dp[m][n];
}

📚 更多经典动态规划案例

4️⃣ 最长公共子序列（LCS）🔗

最长公共子序列是在两个字符串中同时出现的最长子序列。我们可以用动态规划解决，通过定义 dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列的长度。

5️⃣ 最长上升子序列（LIS）📈

最长上升子序列的目标是在一个数组中找到最长的子序列，使得子序列中的每个元素都比前一个元素大⬆️。动态规划通过维护一个状态数组来解决。

6️⃣ 矩阵链乘法问题 🔗✖️

矩阵链乘法问题是为了找到一种最优方式来计算一系列矩阵的乘法次数，使得计算量最少。动态规划可以帮助找到这种最优计算方式。

7️⃣ 最小路径和 🛤️

在一个 m x n 的网格中找到从左上角到右下角的最小路径和🚶。动态规划可以通过定义 dp[i][j] 表示到达位置 (i, j) 的最小路径和来解决。

🤔 动态规划的好处总结

避免重复计算♻️：动态规划通过存储子问题的解来避免重复计算，从而大大降低时间复杂度⏱️。例如，斐波那契数列的暴力求解是 O(2^n)，而动态规划可以做到 O(n)。
自底向上的求解方式⬇️⬆️：动态规划通过从小问题到大问题的解决方法，避免了递归的栈开销，减少了栈溢出的风险⚠️。
适用于重叠子问题和最优子结构的问题💡：很多问题，比如背包问题、编辑距离、最长公共子序列等，都可以用动态规划来高效解决。
时间与空间的平衡⚖️：动态规划通常需要更多的内存，但通过优化可以降低空间复杂度，例如滚动数组📉。
适用范围广🌍：动态规划可以用来解决很多不同类型的问题，从简单的数列到复杂的字符串和路径优化问题。

🔚 结论

动态规划是一种非常强大和有效的算法思想，通过记忆中间结果和从小到大的求解方法，它能够大幅度提高解决问题的效率⏳。希望本文能帮助你理解动态规划的基本概念和如何应用💡。接下来你可以试着练习一些经典的动态规划问题，比如最长上升子序列、完全背包、矩阵链乘、编辑距离、最长公共子序列等。这些问题会帮助你更好地掌握动态规划的思想📚。此外，理解动态规划的优化技巧，比如滚动数组和空间压缩，也会对你解决算法问题大有帮助🛠️💪。

查看全文

http://www.kler.cn/a/379248.html