递归、分治和动态规划

标签：递归 max 分治 43 问题物品动态 dp

递归、分治和动态规划是算法中的三种重要思想，尽管它们有一些相似之处，但在具体实现和应用上有所不同。下面我将逐一讲解这三者的概念和区别。

1. 递归（Recursion）

递归是算法中的一种思想，指的是通过将一个大问题分解为规模较小的相同问题来求解问题。递归通过函数自己调用自己来实现解决方案。递归的关键要点是：

基本情况（Base Case）：即递归的终止条件，避免无限递归。
递推关系：将大问题分解为相似的子问题。

例子：计算斐波那契数列（Fibonacci）

斐波那契数列的递归公式是：

F(n)=F(n−1)+F(n−2)(for n≥2)F(n) = F(n-1) + F(n-2) \quad \text{(for } n \geq 2\text{)}

基本情况：

F(0)=0,F(1)=1F(0) = 0, \quad F(1) = 1

递归实现：

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

2. 分治（Divide and Conquer）

分治法是一种将一个复杂问题分解为多个相同或类似的子问题来逐步求解的策略。分治法通常是递归的，但它的核心思想是通过“分”和“治”两个步骤来解决问题：

分（Divide）：将问题分解成子问题。
治（Conquer）：递归地解决这些子问题，若子问题足够小，则直接求解。
合并（Combine）：将子问题的解合并成原问题的解。

分治法强调的是通过将问题分解为多个独立的小问题来简化求解过程。

例子：归并排序（Merge Sort）

归并排序的核心思想就是将数组分成两半，分别排序，然后合并排序后的两部分：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result.extend(left or right)
    return result

我们来一步步看一下归并排序的计算过程。假设我们要排序的数组是 [38, 27, 43, 3, 9, 82, 10]，我们将按递归步骤和合并过程来演示。

原始数组:

[38, 27, 43, 3, 9, 82, 10]

步骤 1: 分解数组

将数组分成两半，不断递归分割直到每个子数组只有一个元素。

[38, 27, 43, 3, 9, 82, 10] → [38, 27, 43] 和 [3, 9, 82, 10]
[38, 27, 43] → [38] 和 [27, 43]
[27, 43] → [27] 和 [43]
[3, 9, 82, 10] → [3, 9] 和 [82, 10]
[3, 9] → [3] 和 [9]
[82, 10] → [82] 和 [10]

现在我们已经分割到最小的子数组 [38], [27], [43], [3], [9], [82], [10]。

步骤 2: 合并并排序

接下来，我们开始从最小的子数组开始合并。每次合并两个已排序的子数组。

合并 [27] 和 [43] → [27, 43]
合并 [38] 和 [27, 43] → [27, 38, 43]
合并 [3] 和 [9] → [3, 9]
合并 [82] 和 [10] → [10, 82]
合并 [3, 9] 和 [10, 82] → [3, 9, 10, 82]
合并 [27, 38, 43] 和 [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

最终合并结果:

最终的合并结果就是排序后的数组： [3, 9, 10, 27, 38, 43, 82]

3. 动态规划（Dynamic Programming，DP）

动态规划是通过将复杂问题分解为更小的子问题，并保存这些子问题的解，从而避免重复计算相同的子问题。与分治法的区别在于，分治法将问题分解为独立的子问题，而动态规划将问题分解为重叠的子问题，计算时会利用之前计算出的结果。动态规划的关键要点是：

子问题重叠：同一子问题会被多次计算。
状态转移方程：通过递推关系，从已知的解推导出其他解。
记忆化：保存子问题的解，避免重复计算。

动态规划有两种实现方式：

自顶向下（递归+记忆化）：通过递归实现，同时利用一个表格存储已经计算过的结果。
自底向上：从最小的子问题开始，逐步推导出最终的解。

例子：0/1背包问题

假设有 n 个物品，每个物品有一个重量和一个价值，背包的容量是 W，求在不超过背包容量的情况下，能装入背包的最大价值。

动态规划的状态转移方程为：

dp[i][w]=max⁡(dp[i−1][w],dp[i−1][w−wi]+vi)

其中：

dp[i][w] 表示前 i 个物品，背包容量为 w 时的最大价值。
w_i 和 v_i 分别是第 i 个物品的重量和价值。

简而言之，如果作为新增加的物品的此行元素导致了累加质量超过了背包容量的话，就是每列的元素值从上一下抄下来，即舍弃此处新增物品。第一行是第一个物品，第二行是第一、二个物品，第三行是第一、二、三个物品……

动态规划实现：

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

让我们通过一个简单的例子来一步步演示 0/1 背包问题 的动态规划过程。我们假设有 4 个物品，背包容量是 5。

问题设定：

物品数量：4
背包容量：5
物品的重量和价值：
- 物品 1：重量 = 2, 价值 = 3
- 物品 2：重量 = 3, 价值 = 4
- 物品 3：重量 = 4, 价值 = 5
- 物品 4：重量 = 1, 价值 = 2

目标：在不超过背包容量的情况下，选择物品使得背包的总价值最大。

初始化：

我们先创建一个大小为 (n+1) x (W+1) 的二维 DP 表，其中 n 是物品的数量，W 是背包的容量。所有表格元素初始化为 0。

n\w	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	0	0	0	0
2	0	0	0	0	0	0
3	0	0	0	0	0	0
4	0	0	0	0	0	0

填充 DP 表：

物品 1（重量 = 2, 价值 = 3）：

对于容量 w < 2，dp[1][w] 为 0（无法放入物品 1）。
对于容量 w >= 2，dp[1][w] 为物品 1 的价值 3。

n\w	2	3	4	5
0	0	0	0	0
1	3	3	3	3
2	0	0	0	0
3	0	0	0	0
4	0	0	0	0

物品 2（重量 = 3, 价值 = 4）：

对于容量 w < 3，无法放入物品 2，所以 dp[2][w] = dp[1][w]。
对于容量 w >= 3：
- 当 w = 3，可以选择放物品 2，dp[2][3] = max(dp[1][3], dp[1][0] + 4) = max(3, 4) = 4。
- 当 w = 4，可以选择放物品 1 和物品 2，dp[2][4] = max(dp[1][4], dp[1][1] + 4) = max(3, 4) = 4。
- 当 w = 5，可以选择放物品 1 和物品 2，dp[2][5] = max(dp[1][5], dp[1][2] + 4) = max(3, 7) = 7。

n\w	2	3	4	5
0	0	0	0	0
1	3	3	3	3
2	3	4	4	7
3	0	0	0	0
4	0	0	0	0

物品 3（重量 = 4, 价值 = 5）：

对于容量 w < 4，无法放入物品 3，dp[3][w] = dp[2][w]。
对于容量 w >= 4：
- 当 w = 4，可以选择放物品 3，dp[3][4] = max(dp[2][4], dp[2][0] + 5) = max(4, 5) = 5。
- 当 w = 5，可以选择放物品 1 和物品 3，dp[3][5] = max(dp[2][5], dp[2][1] + 5) = max(7, 5) = 7。

n\w	2	3	4	5
0	0	0	0	0
1	3	3	3	3
2	3	4	4	7
3	3	4	5	7
4	0	0	0	0

物品 4（重量 = 1, 价值 = 2）：

对于容量 w < 1，dp[4][w] = dp[3][w]。
对于容量 w >= 1：
- 当 w = 1，可以选择放物品 4，dp[4][1] = max(dp[3][1], dp[3][0] + 2) = max(0, 2) = 2。
- 当 w = 2，可以选择放物品 4 和物品 1，dp[4][2] = max(dp[3][2], dp[3][1] + 2) = max(3, 2) = 3。
- 当 w = 3，可以选择放物品 4 和物品 1，dp[4][3] = max(dp[3][3], dp[3][2] + 2) = max(4, 5) = 5。
- 当 w = 4，可以选择放物品 4 和物品 2，dp[4][4] = max(dp[3][4], dp[3][3] + 2) = max(5, 6) = 6。
- 当 w = 5，可以选择放物品 4 和物品 2，dp[4][5] = max(dp[3][5], dp[3][4] + 2) = max(7, 7) = 7。

n\w	1	2	3	4	5
0	0	0	0	0	0
1	0	3	3	3	3
2	0	3	4	4	7
3	0	3	4	5	7
4	2	3	5	6	7

结果：

最终的最大价值为 dp[4][5] = 7。
选择的物品是：物品 1（重量 2，价值 3）、物品 2（重量 3，价值 4），

总结对比

特性/方法	递归（Recursion）	分治（Divide and Conquer）	动态规划（Dynamic Programming）
定义	通过函数自调用来求解问题	将问题分解为多个子问题，并递归求解	通过存储子问题的结果来避免重复计算
子问题性质	子问题独立	子问题独立	子问题重叠
解决策略	基本情况 + 递推关系	分解问题 + 合并子问题的解	保存子问题解，避免重复计算
应用场景	适合数学递推关系，如斐波那契数列等	适合排序、查找等问题（如归并排序）	适合有重叠子问题的优化问题（如背包问题）
实现方式	递归调用	递归调用 + 合并	递归（带记忆化）或自底向上迭代

总结：

递归是最基础的思想，通常用于处理可以递归分解的问题。
分治通过将问题分解为若干个独立子问题来求解，特别适合排序、查找等问题。
动态规划则是对重叠子问题的一种优化策略，通过记忆化或状态转移来减少计算量，适用于那些存在大量重叠子问题的问题。

标签：递归,max,分治,43,问题,物品,动态,dp
From： https://www.cnblogs.com/zhoushusheng/p/18587070