首页 > 编程语言 >【轻松掌握数据结构与算法】动态规划

【轻松掌握数据结构与算法】动态规划

时间：2025-01-21 12:58:55浏览次数：3  
标签：示例 max 复杂度 算法 轻松 问题 range 数据结构 dp

引言

在本章中，我们将尝试解决那些使用其他技术（例如分治法和贪心法）未能得到最优解的问题。动态规划（DP）是一种简单的技术，但掌握起来可能比较困难。识别和解决DP问题的一个简单方法就是尽可能多地解决各种问题。“编程”一词与编码无关，而是源自文献，意思是填充表格，类似于线性规划。

什么是动态规划策略？

动态规划和记忆化搜索是相辅相成的。分治法和动态规划的主要区别在于，分治法中的子问题是相互独立的，而在DP中子问题可能会重叠。通过使用记忆化搜索（维护一个已解决子问题的表格），动态规划将许多问题的指数级复杂度降低到多项式级复杂度（O(n²)、O(n³)等）。DP的主要组成部分包括：

  • 递归：递归地解决子问题。

  • 记忆化：将已计算的值存储在表格中（记忆化意味着缓存）。 动态规划 = 递归 + 记忆化

动态规划策略的特性

能够判断DP是否能解决给定问题的两个特性是：

  • 最优子结构：一个问题的最优解包含其子问题的最优解。

  • 重叠子问题：递归解中包含少量不同的子问题，这些子问题被重复多次。

动态规划能否解决所有问题？

和贪心法与分治法一样，DP并不能解决所有问题。有些问题无法通过任何算法技术（贪心法、分治法和动态规划）来解决。动态规划与直接递归的区别在于递归调用的记忆化。如果子问题是相互独立且没有重复，那么记忆化就没有帮助，因此动态规划并非所有问题的解决方案。

动态规划方法

解决DP问题主要有两种方法：

  • 自底向上动态规划

  • 自顶向下动态规划

自底向上动态规划

在这种方法中，我们从最小的可能输入参数值开始评估函数，然后逐步增加输入参数值。在计算过程中，我们将所有计算出的值存储在表格（内存）中。当评估较大参数值时，可以使用之前计算出的较小参数值。

示例：斐波那契数列

斐波那契数列中，当前数字是前两个数字的和。斐波那契数列定义如下： F(n)=F(n−1)+F(n−2) 其中，F(0)=0，F(1)=1。

观察斐波那契数列可以发现，当前值仅是前两个计算值的和。这意味着我们无需存储所有先前的值，只需存储最后两个值即可计算当前值。

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

这种实现的时间复杂度为O(n)，空间复杂度为O(1)。

自顶向下动态规划

在这种方法中，我们将问题分解为子问题，解决每个子问题，并记住解决方案，以防需要再次解决。我们还将每个计算出的值作为递归函数的最后一个动作保存，并在第一个动作中检查是否存在预先计算的值。

自底向上与自顶向下编程对比

在自底向上编程中，程序员需要选择要计算的值并决定计算顺序。在这种情况下，所有可能需要的子问题都提前解决，然后用来构建更大问题的解决方案。在自顶向下编程中，原始代码的递归结构得以保留，但避免了不必要的重复计算。问题被分解为子问题，这些子问题被解决并记住，以防需要再次解决。

示例：阶乘问题

阶乘问题：n! 是 n 和 1 之间所有整数的乘积。递归阶乘的定义可以表示为： n!=n×(n−1)! 其中，0!=1。

我们可以使用动态规划来降低复杂度。从递归定义可以看出，fact(n) 是通过 fact(n-1) 和 n 计算得出的。我们可以将之前计算出的值存储在表格中，并使用这些值来计算新值。

def factorial(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0 or n == 1:
        return 1
    memo[n] = n * factorial(n-1, memo)
    return memo[n]

这种实现将复杂度降低到O(max(m,n))。

动态规划算法示例

  • 许多字符串算法，包括最长公共子序列、最长递增子序列、最长公共子串、编辑距离等。

  • 图算法可以高效解决：Bellman-Ford算法用于在图中查找最短距离，Floyd的全对最短路径算法等。

  • 链式矩阵乘法

  • 子集和问题

  • 0/1背包问题

  • 旅行商问题等

理解动态规划

在深入问题之前，让我们通过示例了解DP的工作原理。

1）斐波那契数列

斐波那契数列中，当前数字是前两个数字的和。斐波那契数列定义如下： F(n)=F(n−1)+F(n−2) 其中，F(0)=0，F(1)=1。

递归实现

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

这种递归实现的时间复杂度为指数级，因为它会重复计算许多子问题。

记忆化搜索

为了避免重复计算，我们可以使用记忆化搜索。具体做法是：从递归函数开始，添加一个表格，将函数的参数值映射到函数计算出的结果。如果函数被重复调用且参数相同，我们只需在表格中查找答案即可。

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

这种实现将问题复杂度从指数级降低到多项式级O(n)。

进一步优化

观察斐波那契数列可以发现，当前值仅是前两个计算值的和。这意味着我们无需存储所有先前的值，只需存储最后两个值即可计算当前值。

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

这种实现的时间复杂度为O(n)，空间复杂度为O(1)。

2）阶乘问题

阶乘问题：n! 是 n 和 1 之间所有整数的乘积。递归阶乘的定义可以表示为： n!=n×(n−1)! 其中，0!=1。

递归实现

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n-1)

这种实现的时间复杂度为O(n)，空间复杂度为O(n)，因为递归调用需要一个大小为n的栈。

动态规划优化

我们可以使用动态规划来降低复杂度。从递归定义可以看出，fact(n) 是通过 fact(n-1) 和 n 计算得出的。我们可以将之前计算出的值存储在表格中，并使用这些值来计算新值。

def factorial(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0 or n == 1:
        return 1
    memo[n] = n * factorial(n-1, memo)
    return memo[n]

这种实现将复杂度降低到O(max(m,n))。

3）最长公共子序列

给定两个字符串：长度为m的字符串X [X(1..m)]和长度为n的字符串Y [Y(1..n)]，找到最长公共子序列：在两个字符串中从左到右（但不一定是连续块）出现的最长字符序列。例如，如果X = “ABCBDAB”且Y = “BDCABA”，则LCS(X, Y) = {“BCBA”，“BDAB”，“BCAB”}。我们可以看到有多个最优解。

暴力方法

一个简单的想法是检查X[1.. m]（m是序列X的长度）的每个子序列，看看它是否也是Y[1..n]（n是序列Y的长度）的子序列。 检查需要O(n)时间，而X有2^m个子序列。因此，运行时间是指数级的O(n * 2^m)，对于大型序列来说并不理想。

递归解法

在深入DP解法之前，我们先形成这个问题的递归解法，稍后我们可以添加记忆化来降低复杂度。让我们先对LCS问题进行一些简单观察。如果我们有两个字符串，比如“ABCBDAB”和“BDCABA”，并且我们从第一个字符串的字母画线到第二个字符串的对应字母，那么没有两条线会交叉： 从上述观察中，我们可以看到X和Y的当前字符可能匹配也可能不匹配。这意味着，假设两个首个字符不同。那么它们不可能同时是公共子序列的一部分——其中一个（或者可能两个）将不得不被移除。最后，观察到一旦我们决定了如何处理字符串的首个字符，剩下的子问题又是一个LCS问题，针对两个更短的字符串。因此我们可以递归地解决它。

LCS的解决方案应该找到X和Y中的两个序列，假设序列在X中的起始索引是i，在Y中的起始索引是j。同时，假设X[i...m]是X的一个从字符i开始直到X结尾的子串，Y[j...n]是Y的一个从字符j开始直到Y结尾的子串。 根据上述讨论，我们得到以下可能性：

  1. 如果X[i] == Y[j]：1 + LCS(i+1, j+1)

  2. 如果X[i] ≠ Y[j]：LCS(i, j+1) // 跳过Y的第j个字符

  3. 如果X[i] ≠ Y[j]：LCS(i+1, j) // 跳过X的第i个字符 在第一种情况下，如果X[i]等于Y[j]，我们得到一个匹配对，并可以将其计入LCS的总长度。否则，我们需要跳过X的第i个字符或Y的第j个字符，并找到最长公共子序列。现在，LCS(i, j)可以定义为：

LCS(i,j)=\left\{\begin{matrix} 0, & if&i=m \left | \right |j=n & \\ Max\left \{ LCS(i,j+1),LCS(i+1,j) \right \}, & if &X[i] \neq Y[j] & \\ 1+LCS[i+1,j+1], & if&X[i] == Y[j] \end{matrix}\right.

基于公式的代码实现

以下是基于上述公式的自底向上动态规划实现，以及如何从动态规划表中恢复最长公共子序列。

代码实现
def lcs_length(X, Y):
    m = len(X)
    n = len(Y)
    # 创建一个 (m+1)×(n+1) 的二维数组，初始化为0
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 填充动态规划表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:  # 当前字符匹配
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:  # 当前字符不匹配
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n], dp  # 返回最长公共子序列的长度和动态规划表


def print_lcs(X, Y, dp):
    # 从动态规划表中恢复最长公共子序列
    i = len(X)
    j = len(Y)
    lcs_str = []

    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:  # 当前字符匹配
            lcs_str.append(X[i - 1])  # 添加到LCS中
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:  # 向上移动
            i -= 1
        else:  # 向左移动
            j -= 1

    lcs_str.reverse()  # 反转字符串，因为我们是从后往前构建的
    return ''.join(lcs_str)


# 示例输入
X = "ABCBDAB"
Y = "BDCABA"

# 计算LCS长度
length, dp = lcs_length(X, Y)
print(f"最长公共子序列的长度: {length}")

# 打印LCS
lcs_result = print_lcs(X, Y, dp)
print(f"最长公共子序列: {lcs_result}")
示例输入与输出

输入：

X = "ABCBDAB"
Y = "BDCABA"

输出：

最长公共子序列的长度: 4
最长公共子序列: BCBA

代码解释

  1. 动态规划表的构建：

    • dp[i][j] 表示字符串 X[0...i-1] 和 Y[0...j-1] 的最长公共子序列的长度。

    • 如果 X[i-1] == Y[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。

    • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

  2. 从动态规划表中恢复LCS：

    • 从 dp[m][n] 开始，逐步回溯。

    • 如果 X[i-1] == Y[j-1]，则将该字符加入LCS，并向左上角移动。

    • 否则，根据 dp 表的值决定向上移动还是向左移动。

时间复杂度与空间复杂度

  • 时间复杂度：O(m × n)，其中 m 和 n 分别是字符串 X 和 Y 的长度。

  • 空间复杂度：O(m × n)，用于存储动态规划表。

通过这种方法，我们可以高效地计算出两个字符串的最长公共子序列，同时避免了暴力解法中的指数级复杂度问题。

动态规划：问题与解决方案

动态规划是一种强大的算法设计技术，用于解决具有重叠子问题和最优子结构的问题。通过将问题分解为更小的子问题，并将子问题的解存储起来以避免重复计算，动态规划能够高效地解决许多复杂的优化问题。

1. 0/1 背包问题

问题描述
给定一组物品，每个物品有重量和价值。在不超过背包总容量的前提下，选择物品以最大化背包中的总价值。

示例

  • 物品重量：weights = [2, 3, 4, 5]

  • 物品价值：values = [3, 4, 5, 6]

  • 背包容量：capacity = 5

  • 输出：最大价值 = 7（选择物品1和物品2）

代码实现

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                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][capacity]

# 示例输入输出
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print("最大价值:", knapsack_01(weights, values, capacity))

输出

最大价值: 7

2. 最长递增子序列 (LIS)

问题描述
给定一个整数数组，找到其中最长的严格递增子序列。

示例

  • 输入：arr = [10, 22, 9, 33, 21, 50, 41, 60]

  • 输出：最长递增子序列长度 = 5（例如 [10, 22, 33, 50, 60]）

代码实现

def longest_increasing_subsequence(arr):
    n = len(arr)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

# 示例输入输出
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print("最长递增子序列长度:", longest_increasing_subsequence(arr))

输出

最长递增子序列长度: 5

3. 编辑距离

问题描述
给定两个字符串 str1 和 str2，计算将 str1 转换为 str2 所需的最少操作次数（操作包括插入、删除和替换字符）。

示例

  • 输入：str1 = "horse"，str2 = "ros"

  • 输出：编辑距离 = 3

代码实现

def edit_distance(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    return dp[m][n]

# 示例输入输出
str1 = "horse"
str2 = "ros"
print("编辑距离:", edit_distance(str1, str2))

输出

编辑距离: 3

4. 硬币找零问题

问题描述
给定不同面额的硬币和一个总金额，计算组成该金额所需的最少硬币数量。

示例

  • 硬币面额：coins = [1, 2, 5]

  • 总金额：amount = 11

  • 输出：最少硬币数量 = 3（例如 [5, 5, 1]）

代码实现

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# 示例输入输出
coins = [1, 2, 5]
amount = 11
print("最少硬币数量:", coin_change(coins, amount))

输出

最少硬币数量: 3

5. 矩阵链乘问题

问题描述
给定一组矩阵的维度，计算将这些矩阵依次相乘所需的最小乘法次数。

示例

  • 矩阵维度：p = [10, 20, 30, 40]（表示矩阵 A1: 10×20, A2: 20×30, A3: 30×40）

  • 输出：最小乘法次数 = 30000

代码实现

def matrix_chain_order(p):
    n = len(p) - 1
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1])

    return dp[0][n - 1]

# 示例输入输出
p = [10, 20, 30, 40]
print("最小乘法次数:", matrix_chain_order(p))

输出

最小乘法次数: 30000

6. 最大子数组和

问题描述
给定一个整数数组，找到其中最大子数组的和。

示例

  • 输入：arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

  • 输出：最大子数组和 = 6（例如 [4, -1, 2, 1]）

代码实现

def max_subarray_sum(arr):
    max_ending_here = max_so_far = arr[0]
    for x in arr[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

# 示例输入输出
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("最大子数组和:", max_subarray_sum(arr))

输出

最大子数组和: 6

7. 最小路径和

问题描述
给定一个二维网格，从左上角到右下角的路径中，找到路径和的最小值。每一步只能向下或向右移动。

示例

  • 输入：grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]

  • 输出：最小路径和 = 7

代码实现

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]

    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

    return dp[m - 1][n - 1]

# 示例输入输出
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
print("最小路径和:", min_path_sum(grid))

输出

最小路径和: 7

8. 股票买卖的最佳时机

问题描述
给定一个数组，其中第 i 个元素是第 i 天的股票价格。计算最多进行 k 次交易的最大利润。

示例

  • 输入：prices = [3, 2, 6, 5, 0, 3]，k = 2

  • 输出：最大利润 = 7

代码实现

def max_profit(prices, k):
    n = len(prices)
    if k >= n // 2:
        return sum(max(prices[i + 1] - prices[i], 0) for i in range(n - 1))

    dp = [[0] * n for _ in range(k + 1)]

    for t in range(1, k + 1):
        hold = -prices[0]
        for i in range(1, n):
            dp[t][i] = max(dp[t][i - 1], hold + prices[i])
            hold = max(hold, dp[t - 1][i] - prices[i])

    return dp[k][n - 1]

# 示例输入输出
prices = [3, 2, 6, 5, 0, 3]
k = 2
print("最大利润:", max_profit(prices, k))

输出

最大利润: 7

9. 最小编辑距离（Levenshtein距离）

问题描述
给定两个字符串，计算将一个字符串转换为另一个字符串所需的最少编辑操作次数（包括插入、删除和替换）。

示例

  • 输入：str1 = "kitten"，str2 = "sitting"

  • 输出：最小编辑距离 = 3

代码实现

def min_edit_distance(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    return dp[m][n]

# 示例输入输出
str1 = "kitten"
str2 = "sitting"
print("最小编辑距离:", min_edit_distance(str1, str2))

输出

最小编辑距离: 3

总结

动态规划是一种将复杂问题分解为更简单的子问题，并通过存储子问题的解来避免重复计算的算法设计方法。其核心思想是：“将问题分解为重叠子问题，通过解决子问题并存储其解，来高效地解决原问题。”

标签：示例,max,复杂度,算法,轻松,问题,range,数据结构,dp
From： https://blog.csdn.net/Whoisbug/article/details/145250292

相关文章

  • osgearth夜视效果（粗步实现，夜视算法后续改进）
    夜视效果关键代码 //后期资源 std::string strVertShaderFile="../EarthData/Shaders/Post/Post.vert.glsl"; std::string strFragShaderFile="../EarthData/Shaders/Post/Post.frag.glsl"; std::string strPostImageFile="../EarthData/Texture/Ra......
  • K8s 灰度发布实战：通过 Ingress 注解轻松实现流量分割与渐进式发布
    在现代微服务架构中，应用的更新和发布是一个高频且关键的操作。如何在不影响用户体验的前提下，安全、平稳地将新版本应用推送到生产环境，是每个开发者和运维团队必须面对的挑战。灰度发布（GrayRelease）作为一种渐进式发布策略，能够有效降低发布风险，而Kubernetes的Ingress注解功能为......
  • 单调队列：实用而好写的数据结构
    前言|Preface这几天连续做了好几道单调队列的题，难度从绿到蓝不等，摸索出了一些经验，也总结了一些单调队列的特点和规律。概述|Outline顾名思义，单调队列的重点分为「单调」和「队列」。「单调」指的是元素的「规律」——递增（或递减）。「队列」指的是元素只能从队头和队尾进......
  • 掌握这些技巧，让你轻松应对网站模板修改中的常见挑战
    注意事项解释遵循最佳实践始终按照官方文档推荐的方式来进行修改，避免直接编辑核心文件，以减少升级时出现问题的风险。考虑SEO影响模板中的元标签、标题标签等元素直接影响搜索引擎抓取效率，因此在修改时要格外小心，确保不会破坏原有SEO设置。维护一致性整个网站应......
  • 数据结构与算法之递归: LeetCode 39. 组合总和 (Ts版)
    组合总和https://leetcode.cn/problems/combination-sum/description/描述给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合candid......
  • 01 序论（数据结构实战）
    计算机的发展与用途：早期的计算机：最初，计算机主要是用来进行数学运算，像是加减乘除这种“数值计算”。它们主要用在科学研究、工程计算等需要大量数字计算的领域。现在的计算机：现代的计算机用途广泛，已经不仅仅局限于处理数字。它们还处理许多其他类型的数据，比如文字、表格、图片......
  • 第四天算法设计
    希尔排序需求：排序前：{9,1,2,5,7,4,8,6,3,5}排序后：{1,2,3,4,5,5,6,7,8,9}算法设计Shell类：packagesuanfa;publicclassShell{publicstaticvoidsort(Comparable[]a){//先确定增长量inth=1;while(h<a.length/2){h=2*h+1;}......
  • 【高创新】基于matlab斑马算法ZOA-CNN-LSTM-Attention用客流量预测【含Matlab源码 842
    ......
  • 跨境图片翻译工具，轻松玩转外贸电商
    最近做外贸的小伙伴们是不是经常遇到这样的困扰？客户发来的图片看不懂，产品包装上的文字需要翻译，甚至连供应商寄来的样品说明书也是外语。搞不清楚内容，沟通效率直接拉胯。你可能会想，“这点小事用翻译软件不就行了？”但问题是，有些翻译工具只能处理纯文本，遇到图片上的文字就无能为力......
  • 数据结构-堆及堆排序
    1.堆的定义堆（Heap）是一种数据结构，通常是一个完全二叉树。在堆中，每个节点都有一个与其相关的值，并且满足堆的性质。堆分为两种类型：大堆和小堆。大堆：在大堆中，对于每个非叶子节点，其值都大于或等于它的子节点的值。也就是说，根节点的值是整个堆中的最大值。小堆：与大堆相反，在小堆中，对......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99