程序员应该了解的动态规划算法

动态规划是计算机科学和软件工程领域中一种流行的技术，在算法竞赛中扮演着至关重要的角色。它通过将复杂问题分解成更小的子问题来解决，每个子问题只需求解一次，并将子问题的解存储起来以便在需要时重复使用。在本篇博客中，我们将探讨每位算法竞赛选手都应该掌握的必要动态规划算法。

斐波那契数列

斐波那契数列是一个著名的数列，其定义式为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(p):
    n = len(p) - 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][k] + m[k+1][j] + p[i] * p[k+1] * p[j+1]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k

    return m, s

最长递增子序列

最长递增子序列（LIS）问题是指找到给定序列中严格递增的最长子序列。该问题可以通过动态规划求解，即将其分解为若干个子问题，每个子问题只需求解一次。LIS 问题在现实世界中有着广泛的应用，例如数据压缩、模式识别和生物信息学。

def lis(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)

旅行商问题

旅行商问题（TSP）旨在找到一条经过给定城市集合并最终返回出发城市的最短路径。该问题可以通过动态规划求解，即将其分解为若干个子问题，每个子问题只需求解一次。TSP 是计算机科学中的一个经典问题，在物流、运输和网络优化等领域有着广泛的实际应用。

def tsp(graph, start):
    n = len(graph)
    visited = (1 << n) - 1
    memo = {}

    def dfs(node, visited):
        if visited == 0:
            return graph[node][start]

        if (node, visited) in memo:
            return memo[(node, visited)]

        ans = float('inf')
        for i in range(n):
            if visited & (1 << i):
                ans = min(ans, graph[node][i] + dfs(i, visited ^ (1 << i)))

        memo[(node, visited)] = ans
        return ans

    return dfs(start, visited)

0-1整数规划

0-1整数规划问题是指在满足一系列约束条件的前提下，寻找一组二元决策变量的最优解。该问题可以通过动态规划求解，即将其分解为若干个子问题，每个子问题只需求解一次。0-1整数规划问题在现实世界中有着广泛的应用，例如资源分配、调度和生产计划。

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_with_allowed_ops(s1, s2, allowed_ops):
    m, n = len(s1), len(s2)
    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 s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            elif allowed_ops.get((s1[i-1], s2[j-1])):
                op_cost = allowed_ops[(s1[i-1], s2[j-1])]
                dp[i][j] = min(dp[i-1][j] + op_cost[0], dp[i][j-1] + op_cost[1], dp[i-1][j-1] + op_cost[2])
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

    return dp[m][n]

最长的回文子字符串

最长回文子串问题是指找到给定字符串中最长的回文子串。这个问题可以通过动态规划来解决，即将其分解为若干个子问题，每个子问题只需求解一次。

def longest_palindromic_substring(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    max_len = 1
    start = 0

    for i in range(n):
        dp[i][i] = True

    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1

            if l == 2:
                dp[i][j] = s[i] == s[j]
            else:
                dp[i][j] = s[i] == s[j] and dp[i+1][j-1]

            if dp[i][j] and l > max_len:
                max_len = l
                start = i

    return s[start:start+max_len]

最大乘积子阵列

最大乘积子数组问题是指在一个一维数字数组中找到乘积最大的连续子数组。这个问题可以通过动态规划来解决，即将其分解为若干个子问题，每个子问题只需求解一次。

def max_product_subarray(nums):
    n = len(nums)
    max_prod = nums[0]
    min_prod = nums[0]
    max_so_far = nums[0]

    for i in range(1, n):
        temp = max_prod
        max_prod = max(nums[i], max(nums[i] * max_prod, nums[i] * min_prod))
        min_prod = min(nums[i], min(nums[i] * temp, nums[i] * min_prod))
        max_so_far = max(max_so_far, max_prod)

    return max_so_far

直方图中的最大矩形

直方图中最大矩形问题是指在由不同高度矩形组成的直方图中，找到能够构成的最大矩形。该问题可以通过动态规划来解决，即将其分解为若干个子问题，每个子问题只需求解一次。

def largest_rectangle_area(heights):
    n = len(heights)
    left = [0] * n
    right = [0] * n
    stack = []

    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()

        left[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []
    for i in range(n-1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()

        right[i] = stack[-1] if stack else n
        stack.append(i)

    max_area = 0
    for i in range(n):
        max_area = max(max_area, heights[i] * (right[i] - left[i] - 1))

    return max_area

鸡蛋掉落问题

鸡蛋掉落问题是指找出鸡蛋能够不破裂地从哪个楼层掉落所需的最少尝试次数。这个问题可以通过动态规划来解决，即将其分解成若干个子问题，每个子问题只需求解一次。

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

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

    for j in range(1, k+1):
        dp[1][j] = j

    for i in range(2, n+1):
        for j in range(2, k+1):
            dp[i][j] = float('inf')
            for x in range(1, j+1):
                res = 1 + max(dp[i-1][x-1], dp[i][j-x])
                dp[i][j] = min(dp[i][j], res)

    return dp[n][k]

计数位

计数位问题是指找出从 0 到 n 的每个数字的二进制表示中 1 的个数。这个问题可以通过动态规划来解决，方法是将其分解成更小的子问题，每个子问题只需解决一次。

def count_bits(n):
    dp = [0] * (n+1)

    for i in range(1, n+1):
        dp[i] = dp[i >> 1] + (i & 1)

    return dp

完全平方数

完全平方数问题是指找出和等于给定数的最少完全平方数个数。这个问题可以用动态规划来解决，方法是将完全平方数分解成若干个子问题，每个子问题只需求解一次。

def num_squares(n):
    dp = [float('inf')] * (n+1)
    dp[0] = 0

    for i in range(1, n+1):
        j = 1
        while j*j <= i:
            dp[i] = min(dp[i], dp[i-j*j] + 1)
            j += 1

    return dp[n]

划分相等子集和

等子集和划分问题是指判断给定的集合是否可以划分成两个子集，使得两个子集元素的和相等。这个问题可以通过动态规划来解决，即将其分解成若干个子问题，每个子问题只需求解一次。

def can_partition(nums):
    n = len(nums)
    s = sum(nums)

    if s % 2 != 0:
        return False

    target = s // 2
    dp = [False] * (target+1)
    dp[0] = True

    for i in range(1, n+1):
        for j in range(target, nums[i-1]-1, -1):
            dp[j] |= dp[j-nums[i-1]]

    return dp[target]

最长公共子字符串

最长公共子串问题是指找到两个给定字符串共有的最长子串。这个问题可以通过动态规划来解决，即将其分解为若干个子问题，每个子问题只需求解一次。

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    max_len = 0

    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
                max_len = max(max_len, dp[i][j])

    return max_len

独特路径

唯一路径问题是指在网格中，从左上角到右下角存在多少条唯一路径m x n，且只能向下或向右移动。这个问题可以通过动态规划来解决，即将其分解为若干个子问题，每个子问题只需求解一次。

def unique_paths(m, n):
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

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

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

使用允许的操作编辑距离

def edit_distance_with_allowed_ops(s1, s2, allowed_ops):
    m, n = len(s1), len(s2)
    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 s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            elif allowed_ops.get((s1[i-1], s2[j-1])):
                op_cost = allowed_ops[(s1[i-1], s2[j-1])]
                dp[i][j] = min(dp[i-1][j] + op_cost[0], dp[i][j-1] + op_cost[1], dp[i-1][j-1] + op_cost[2])
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

    return dp[m][n]

子集和问题

子集和问题是指判断给定整数集合是否存在一个子集，其中所有元素的和等于给定的值。这个问题可以通过动态规划来解决，即将其分解为若干个子问题，每个子问题只需求解一次。

def subset_sum(nums, target):
    n = len(nums)
    dp = [[False] * (target+1) for _ in range(n+1)]

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

    for i in range(1, n+1):
        for j in range(1, target+1):
            if nums[i-1] <= j:
                dp[i][j] = dp[i-1][j-nums[i-1]] or dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][target]

最长的回文子字符串

def longest_palindromic_substring(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    max_len = 1
    start = 0

    for i in range(n):
        dp[i][i] = True

    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1

            if l == 2:
                dp[i][j] = s[i] == s[j]
            else:
                dp[i][j] = s[i] == s[j] and dp[i+1][j-1]

            if dp[i][j] and l > max_len:
                max_len = l
                start = i

    return s[start:start+max_len]

最长的回文子序列

最长回文子序列问题是指找到给定字符串中最长的回文子序列。这个问题可以通过动态规划来解决，即将其分解为若干个子问题，每个子问题只需求解一次。

def longest_palindromic_subsequence(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1

            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])

    return dp[0][n-1]

最大乘积子阵列

def max_product_subarray(nums):
    n = len(nums)
    max_prod = nums[0]
    min_prod = nums[0]
    max_so_far = nums[0]

    for i in range(1, n):
        temp = max_prod
        max_prod = max(nums[i], max(nums[i] * max_prod, nums[i] * min_prod))
        min_prod = min(nums[i], min(nums[i] * temp, nums[i] * min_prod))
        max_so_far = max(max_so_far, max_prod)

    return max_so_far

直方图中的最大矩形

def largest_rectangle_area(heights):
    n = len(heights)
    left = [0] * n
    right = [0] * n
    stack = []

    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()

        left[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []
    for i in range(n-1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()

        right[i] = stack[-1] if stack else n
        stack.append(i)

    max_area = 0
    for i in range(n):
        max_area = max(max_area, heights[i] * (right[i] - left[i] - 1))

    return max_area

鸡蛋掉落问题

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

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

    for j in range(1, k+1):
        dp[1][j] = j

    for i in range(2, n+1):
        for j in range(2, k+1):
            dp[i][j] = float('inf')
            for x in range(1, j+1):
                res = 1 + max(dp[i-1][x-1], dp[i][j-x])
                dp[i][j] = min(dp[i][j], res)

    return dp[n][k]

计数位

def count_bits(n):
    dp = [0] * (n+1)

    for i in range(1, n+1):
        dp[i] = dp[i >> 1] + (i & 1)

    return dp

完全平方数

def num_squares(n):
    dp = [float('inf')] * (n+1)
    dp[0] = 0

    for i in range(1, n+1):
        j = 1
        while j*j <= i:
            dp[i] = min(dp[i], dp[i-j*j] + 1)
            j += 1

    return dp[n]

划分相等子集和

def can_partition(nums):
    n = len(nums)
    s = sum(nums)

    if s % 2 != 0:
        return False

    target = s // 2
    dp = [False] * (target+1)
    dp[0] = True

    for i in range(1, n+1):
        for j in range(target, nums[i-1]-1, -1):
            dp[j] |= dp[j-nums[i-1]]

    return dp[target]

独特路径

def unique_paths(m, n):
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

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

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

独特路径 II

唯一路径 II 问题是唯一路径问题的一个变体，其中网格中的某些单元格被阻挡，无法通行。该问题的目标是找到从网格左上角到右下角的唯一路径数量，路径只能向下或向右移动，不能经过被阻挡的单元格。该问题可以使用动态规划来解决，方法是将其分解为若干个子问题，每个子问题只需求解一次。

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

    if obstacle_grid[0][0] == 0:
        dp[0][0] = 1

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

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

结论

动态规划是一种强大的技术，对于解决竞技编程中的许多复杂问题至关重要。本博客讨论的算法只是动态规划能够解决的众多问题中的一小部分。通过掌握这些算法并理解其基本原理，您可以成为更优秀的竞技程序员，并解决更具挑战性的问题。

文章来源：https://dev.to/rishitashaw/dynamic-programming-algorithms-every-programmer-should-know-3915

分享

程序员应该了解的动态规划算法

程序员应该了解的动态规划算法

斐波那契数列

最长公共子序列

背包问题

编辑距离

最大子阵列

零钱

矩阵链乘法

最长递增子序列

旅行商问题

0-1整数规划

使用允许的操作编辑距离

最长的回文子字符串

最大乘积子阵列

直方图中的最大矩形

鸡蛋掉落问题

计数位

完全平方数

划分相等子集和

最长公共子字符串

独特路径

使用允许的操作编辑距离

子集和问题

最长的回文子字符串

最长的回文子序列

最大乘积子阵列

直方图中的最大矩形

鸡蛋掉落问题

计数位

完全平方数

划分相等子集和

独特路径

独特路径 II

结论