正文

掌握动态规划，只需牢记这五大基本框架

/0 浏览量
0201

动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。掌握动态规划的关键在于理解其基本框架，以下是五大基本的动态规划框架，助你快速掌握这门技巧。

一、自底向上的框架

1.1 原理

自底向上的框架是从子问题开始，逐步解决更复杂的问题，直到得到原始问题的解。这种方法的优点是易于理解，逻辑清晰。

1.2 示例

问题：计算斐波那契数列的第n项。

def fibonacci(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

二、自顶向下的框架

2.1 原理

自顶向下的框架是从原始问题开始，将其分解为子问题，并递归求解子问题。这种方法的优点是容易实现，但递归过程可能导致大量的重复计算。

2.2 示例

问题：计算斐波那契数列的第n项。

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

三、记忆化递归框架

3.1 原理

记忆化递归框架是在自顶向下的基础上，通过保存已计算过的子问题结果来避免重复计算。这种方法适用于递归过程中有大量重复计算的问题。

3.2 示例

问题：计算斐波那契数列的第n项。

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

四、动态规划表框架

4.1 原理

动态规划表框架是将子问题及其解存储在二维数组（或列表）中，从而实现自底向上的递推。这种方法在解决线性问题（如最长公共子序列）时非常有效。

4.2 示例

问题：计算最长公共子序列。

def longest_common_subsequence(X, Y):
    m, n = len(X), len(Y)
    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]

五、状态压缩框架

5.1 原理

状态压缩框架将状态空间中的状态压缩到整数中，从而简化问题。这种方法适用于状态空间较大且状态之间关系复杂的问题。

5.2 示例

问题：求解0-1背包问题。

def knapsack(W, N, WTS):
    # 初始化动态规划表
    dp = [0] * (W + 1)
    for i in range(1, W + 1):
        for j in range(1, N + 1):
            # 获取当前物品的状态
            state = 1 << j
            # 状态压缩，保留前j个物品的状态
            state |= dp[i]
            # 判断当前物品是否可以放入背包
            if i >= WTS[j - 1] and (state & (1 << (j - 1))) == 0:
                # 更新当前物品的状态
                dp[i] = state | (1 << j)
                # 更新背包中物品的总重量
                dp[i] = dp[i - WTS[j - 1]] | (1 << j)
    # 计算背包中物品的总价值
    value = sum((1 << j) for j in range(N) if dp[W] & (1 << j))
    return value

通过掌握这五大基本框架，你可以更好地理解和应用动态规划，解决各种复杂问题。在实际应用中，可以根据具体问题选择合适的框架，并不断优化算法性能。

-- 展开阅读全文 --