动态规划基础：最强的算法技巧，助你征服复杂问题！

动态规划（Dynamic Programming，简称DP）是一种非常强大的算法设计技巧，适用于解决那些可以被分解为子问题的问题。它通过记忆化（记住已经解决的子问题的结果）来避免重复计算，从而有效地提高算法的性能。接下来，我们将通过一些简单易懂的例子来深入理解动态规划的基本概念和应用。

什么是动态规划？

动态规划主要用于解决具有重叠子问题和最优子结构性质的问题。简单来说，就是将复杂的问题分解成更小的、相似的子问题，并存储这些子问题的解以便后续使用。

重叠子问题：当一个问题可以被分解为多个相同的子问题时，这些子问题会在不同的计算中重复出现。
最优子结构：一个问题的最优解可以通过其子问题的最优解构建而成。

动态规划的基本步骤

定义子问题：明确要解决的子问题是什么。
状态转移方程：找出子问题之间的关系，建立状态转移方程。
边界条件：设定初始条件。
计算并存储结果：按照一定的顺序计算出所有子问题的解，并存储它们以便复用。

例子1：斐波那契数列

斐波那契数列是动态规划最经典的例子之一。这个数列的定义如下：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) （n >= 2）

递归实现（没有动态规划）

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

print(fibonacci(10))  # 输出 55

以上实现虽然简单，但是会重复计算许多子问题，时间复杂度为 (O(2^n))。

动态规划实现

def fibonacci_dp(n):
    if n <= 1:
        return n
    fib = [0] * (n + 1)
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]

print(fibonacci_dp(10))  # 输出 55

在这个动态规划的实现中，我们用一个数组 fib 来存储已经计算的斐波那契数，避免了重复计算。时间复杂度降到了 (O(n))。

例子2：最小路径和

另一个经典的动态规划问题是“最小路径和”。给定一个二维网格（矩阵），从左上角到右下角的最小路径和是多少？只能向右和向下移动。

问题描述

假设有如下的网格：

[
 [2, 1, 3],
 [6, 5, 4],
 [7, 8, 9]
]

我们需要找到从左上角到右下角的最小路径和。

动态规划实现

def min_path_sum(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]

    dp[0][0] = grid[0][0]

    for i in range(1, rows):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, cols):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[rows-1][cols-1]

grid = [
    [2, 1, 3],
    [6, 5, 4],
    [7, 8, 9]
]
print(min_path_sum(grid))  # 输出 16

在这个例子中，我们使用一个 dp 数组来记录从起点到每个格子的最小路径和。时间复杂度为 (O(m times n))，其中 (m) 是行数，(n) 是列数。

例子3：0-1背包问题

背包问题是动态规划中的经典问题之一。给定一组物品，每个物品都有重量和价值，目标是在不超过背包最大容量的情况下，选择物品使得总价值最大。

问题描述

假设我们有如下物品：

物品1：重量2，价值3
物品2：重量3，价值4
物品3：重量4，价值5
物品4：重量5，价值6

背包最大容量为5。

动态规划实现

def knapsack(weights, values, capacity):
    n = len(values)
    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]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity))  # 输出 7