动态规划（Dynamic Programming，简称DP），它是一种通过将复杂问题分解为更小的子问题来求解问题的方法，有点类似于分治算法的思想。它特别适用于那些通过重叠子问题（Overlapping Subproblems）和最优子结构（Optimal Substructure）性质可以被高效解决的问题。

动态规划的基本思想

重叠子问题

所谓的重叠子问题，其实是将原问题分解为若干类似的子问题，这些子问题的计算过程在整个的求解过程中会被多次重复计算。

最优子结构

所谓的最优子结构，意思是说原问题的最优解就包含其子问题的最优解中。

子问题的状态和状态转移

通过对已经解决的子问题的结果或者是状态进行保存，来避免对于问题操作的重复计算通过状态转移方程，也被称为是递推的关系来逐步的求解原问题的解。

通过利用上面的思路，我们可以总结出如下的两种实现方式。

  • 自顶向下的记忆化搜索（递归 + 记忆化）
  • 自底向上的递推（迭代）

下面我们就结合具体的例子来理解一下动态规划算法。

斐波那契数列

斐波那契数列是一个最简单的动态规划问题，它满足重叠子问题和最优子结构的性质。我们可以通过递归 + 记忆化的方法来实现，如下所示。

1
2
3
4
5
6
7
8
9
10
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]

# 使用示例
print(fib_memo(10))  # 输出55

自底向上的递推方法

1
2
3
4
5
6
7
8
9
10
11
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]

# 使用示例
print(fib_dp(10))  # 输出55

背包问题

背包问题是动态规划的经典应用之一。假设我们有一个容量为W 的背包和n 件物品，每件物品有一个重量和一个价值，目标是让背包中的物品总价值最大化。

0-1 背包问题的动态规划实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, W + 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][W]

# 使用示例
weights = [1, 2, 3]
values = [10, 15, 40]
W = 5
print(knapsack(weights, values, W))  # 输出55

总结

动态规划算法是一种很难理解，但是又非常强大且高效的算法设计思路，适用于很多问题的最优解求解，该算法的核心其实就是在于对问题中的重叠子问题和最优子结构进行识别，然后通过利用状态和状态转移方程高效求解。在实际编程中，选择合适的存储结构和优化计算顺序可以进一步提升动态规划算法的效率。