Python 动态规划算法学习的经典案例

xiaoshi 05-30 17 抢沙发

默认

摘要： ...

Python动态规划算法学习：从入门到精通的经典案例解析

动态规划（Dynamic Programming, DP）是算法设计中一种强大的方法，特别适合解决具有重叠子问题和最优子结构性质的问题。对于Python开发者而言，掌握动态规划不仅能提升算法能力，还能在面试和实际项目中解决复杂问题。本文将介绍几个经典的动态规划案例，帮助你从零开始理解并应用这一重要算法。

什么是动态规划？

动态规划是一种分阶段解决问题的方法，它将复杂问题分解为更小的子问题，通过存储子问题的解来避免重复计算，从而提高效率。动态规划通常用于优化问题，如寻找最大值、最小值或最优路径等。

动态规划的核心思想可以概括为三点：

分治：将原问题分解为相似的子问题
记忆化：存储子问题的解以避免重复计算
递推：利用已存储的子问题解构建原问题的解

经典案例1：斐波那契数列

斐波那契数列是理解动态规划最直观的例子。数列定义为：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2）。

递归解法的问题

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

这种递归解法虽然简单，但效率极低，时间复杂度为O(2^n)，因为存在大量重复计算。

动态规划解法

def fib_dp(n):
    if n <= 1:
        return 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]

这种方法将时间复杂度降为O(n)，空间复杂度也是O(n)。进一步优化，可以只保存前两个状态，将空间复杂度降为O(1)：

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

经典案例2：背包问题

背包问题是动态规划的经典应用场景。给定一组物品，每个物品有重量和价值，在不超过背包承重的情况下，如何选择物品使总价值最大。

0-1背包问题

在0-1背包问题中，每种物品只能选择拿或不拿。

def knapsack(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(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

空间优化版本

def knapsack_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])

    return dp[capacity]

经典案例3：最长公共子序列(LCS)

最长公共子序列问题要求找出两个序列共有的最长子序列的长度，子序列不需要连续。

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

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

经典案例4：硬币找零问题

给定不同面额的硬币和一个总金额，计算凑成总金额所需的最少硬币数。

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

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

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