动态规划算法从入门到精通

动态规划（Dynamic Programming）是解决最优化问题的重要算法范式，通过将大问题分解为重叠子问题来高效求解。

核心思想

最优子结构：问题的最优解包含子问题的最优解
重叠子问题：子问题会被重复计算

经典问题：斐波那契数列

递归解法（低效）

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
# 时间复杂度 O(2^n)

记忆化搜索

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]
# 时间复杂度 O(n)

自底向上 DP

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]

背包问题

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(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]

掌握动态规划的关键在于识别问题的子结构并定义合适的状态转移方程。