每个程序员都应该知道的动态规划算法

た入场券 2023-09-26 22:13 75阅读 0赞

动态编程是计算机科学和软件工程中的一种流行技术，在竞争性编程中起着至关重要的作用。它是一种解决复杂问题的方法，方法是将复杂问题分解为更小的子问题，每个子问题只求解一次，存储子问题的解，以便在需要时可以重复使用。在这篇博客中，我们将探讨每个有竞争力的程序员都应该知道的必要的动态规划算法。

斐波那契数列  
斐波那契数列是一个众所周知的数列，由递推关系 定义F(n) = F(n-1) + F(n-2)，基本情况F(0) = 0和F(1) = 1。计算斐波那契数列的简单递归算法是直接使用递归关系，但这会导致指数时间复杂度。动态规划允许我们通过使用记忆化在线性时间内解决这个问题，记忆化存储已经解决的子问题的结果。  
def fibonacci(n, memo):  
if n in memo:  
return memo\[n\]  
if n <= 1:  
memo\[n\] = n  
else:  
memo\[n\] = fibonacci(n-1, memo) + fibonacci(n-2, memo)  
return memo\[n\]

最长公共子序列  
最长公共子序列 (LCS) 问题是一个经典的动态规划问题，涉及寻找两个给定字符串共有的最长子序列。字符串的子序列是在字符串中以相同顺序出现但不一定连续出现的字符序列。LCS 问题可以使用动态规划来解决，方法是将其分解为更小的子问题并且每个子问题仅求解一次。  
def lcs(s1, s2):  
m, n = len(s1), len(s2)  
dp = \[\[0\] \* (n+1) for \_ in range(m+1)\]

for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[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]

背包问题  
背包问题是一个经典的优化问题，它涉及找到最优的物品子集以将其装入容量有限的背包中，从而使所装物品的价值最大化。这个问题也可以使用动态规划来解决，方法是将它分解成更小的子问题并且每个子问题只解决一次。  
def knapsack(W, wt, val, n):  
dp = \[\[0\] \* (W+1) for \_ in range(n+1)\]

for i in range(1, n+1):
        for w in range(1, W+1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

编辑距离  
编辑距离问题涉及找到将一个字符串转换为另一个字符串所需的最少操作数。允许的操作是插入、删除和替换。这个问题可以使用动态规划来解决，方法是将它分解成更小的子问题并且每个子问题只解决一次。  
def edit\_distance(s1, s2):  
m, n = len(s1), len(s2)  
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 s1[i-1] == s2[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]

最大子数组  
最大子数组问题涉及在一维数字数组中找到具有最大总和的连续子数组。这个问题可以使用动态规划来解决，方法是将它分解成更小的子问题并且每个子问题只解决一次。  
def max\_subarray(arr):  
n = len(arr)  
max\_sum = float(‘-inf’)  
current\_sum = 0

for i in range(n):
        current_sum += arr[i]
        max_sum = max(max_sum, current_sum)
        current_sum = max(current_sum, 0)
    
    return max_sum

零钱  
硬币找零问题涉及使用给定的一组硬币面额找到给定数量的货币进行找零的方法的数量。这个问题可以使用动态规划来解决，方法是将它分解成更小的子问题并且每个子问题只解决一次。  
def coin\_change(coins, amount):  
dp = \[float(‘inf’)\] \* (amount+1)  
dp\[0\] = 0

for i in range(1, amount+1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i-coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

矩阵链乘法  
矩阵链乘法问题涉及找到将一系列矩阵相乘的最佳方法。这个问题可以使用动态规划来解决，方法是将它分解成更小的子问题并且每个子问题只解决一次。它是动态规划的一个经典例子，被用于许多领域，例如计算机图形学、数值分析和科学计算。  
def matrix\_chain\_order§:  
n = len§ - 1  
m = \[\[float(‘inf’)\] \* n for \_ in range(n)\]  
s = \[\[0\] \* n for \_ in range(n)\]

for i in range(n):
        m[i][i] = 0
    
    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            for k in range(i, j):
                q = m[i]