1. 分治法（Divide and Conquer）

1.1 分治法的基本思想

分治法的基本思想是：将一个规模为 $n$ 的问题分解为 $k$ 个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

分治法的三个步骤：

  1. 分解（Divide）：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题
  2. 解决（Conquer）：若子问题规模较小而容易被解决则直接解，否则递归地解各子问题
  3. 合并（Combine）：将各子问题的解合并为原问题的解

1.2 实例：最大子段和问题

问题描述：给定由 $n$ 个整数（可能有负整数）组成的序列 $a_1, a_2, …, a_n$，求该序列的子段和的最大值。

分治策略：

将序列分成左右两半，最大子段和可能出现在：

  • 左半部分
  • 右半部分
  • 跨越中间点

C++ 代码实现：

#include <stdio.h>
#include <stdlib.h>

int MaxSubSum(int *Array, int left, int right) {
    int sum = 0;
    int i;

    if (left == right) {
        if (Array[left] > 0)
            sum = Array[left];
        else
            sum = 0;
    } else {
        int center = (left + right) / 2;
        int leftSum = MaxSubSum(Array, left, center);
        int rightSum = MaxSubSum(Array, center + 1, right);

        // 计算跨越中间点的最大子段和
        int s1 = 0;
        int lefts = 0;
        for (i = center; i >= left; i--) {
            lefts += Array[i];
            if (lefts > s1)
                s1 = lefts;
        }

        int s2 = 0;
        int rights = 0;
        for (i = center + 1; i <= right; i++) {
            rights += Array[i];
            if (rights > s2)
                s2 = rights;
        }

        sum = s1 + s2;

        if (sum < leftSum)
            sum = leftSum;

        if (sum < rightSum)
            sum = rightSum;
    }

    return sum;
}

int main() {
    int *Array = (int *) malloc(6 * sizeof(int));
    Array[0] = -2;
    Array[1] = 11;
    Array[2] = -4;
    Array[3] = 13;
    Array[4] = -5;
    Array[5] = -2;

    int result = MaxSubSum(Array, 0, 5);
    printf("%d", result);

    return 0;
}

2. 动态规划法（Dynamic Programming）

2.1 动态规划法的基本思想

动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法的区别：

  • 分治法：子问题相互独立
  • 动态规划：子问题有重叠，使用备忘录（表格）保存已解决的子问题的答案

动态规划法的两个重要性质：

  1. 最优子结构：问题的最优解包含其子问题的最优解
  2. 重叠子问题：递归算法反复求解相同的子问题

设计一个动态规划算法的步骤：

  1. 找出最优解的性质，并刻画其结构特征
  2. 递归地定义最优值
  3. 以自底向上的方式计算出最优值
  4. 根据计算最优值时得到的信息，构造最优解

2.2 实例：0-1背包问题

问题描述：给定 $n$ 种物品和一个容量为 $W$ 的背包，物品 $i$ 的重量为 $w_i$，价值为 $v_i$。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？

0-1背包问题的特点：对于每种物品，要么装入背包，要么不装入，不能只装入一部分。

动态规划解法：

设 $f[i][j]$ 表示从前 $i$ 个物品中选择，放入容量为 $j$ 的背包中所能获得的最大价值。

状态转移方程：

$$f[i][j] = \max(f[i-1][j], f[i-1][j-w_i] + v_i)$$

其中：

  • $f[i-1][j]$：不选第 $i$ 个物品
  • $f[i-1][j-w_i] + v_i$：选第 $i$ 个物品（前提是 $j \geq w_i$）

C++ 代码实现：

#include <stdio.h>

#define N 4 // 物品数量
#define W 5 // 背包容量

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int v[] = {0, 2, 4, 5, 6}; // 物品价值数组
    int w[] = {0, 1, 2, 3, 4}; // 物品重量数组

    int f[N + 1][W + 1] = {}; // 子问题解数组

    int i, j;
    for (i = 1; i <= N; i++) {
        for (j = 1; j <= W; j++) {
            f[i][j] = f[i - 1][j]; // 默认不选第 i 个物品

            if (j >= w[i]) { // 选第 i 个物品的前提条件
                // 等于 不选第 i 个物品 和 选第 i 个物品 两者的较大值
                f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
            }
        }
    }

    printf("%d\n", f[N][W]);

    // 打印DP表格
    for (i = 0; i <= N; i++) {
        for (j = 0; j <= W; j++) {
            printf("%d ", f[i][j]);
        }
        printf("\n");
    }

    return 0;
}

另一种写法：

if (j >= w[i]) { // 选第 i 个物品的前提条件
    f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
} else { // 不选第 i 个物品
    f[i][j] = f[i - 1][j];
}

3. 分治法与动态规划的比较

特性 分治法 动态规划
子问题关系 子问题相互独立 子问题有重叠
求解方式 自顶向下递归求解 自底向上填表求解
存储需求 不需要存储子问题解 需要存储子问题解（备忘录）
适用场景 子问题不重复的问题 子问题重复的问题
典型问题 归并排序、快速排序、最大子段和 0-1背包、最长公共子序列、矩阵链乘

4. 其他经典动态规划问题

4.1 最长公共子序列（LCS）

给定两个序列 $X$ 和 $Y$，找出它们的最长公共子序列的长度。

状态转移方程：

$$c[i][j] = \begin{cases} 0 & i=0 \text{ 或 } j=0 \ c[i-1][j-1]+1 & x_i = y_j \ \max(c[i-1][j], c[i][j-1]) & x_i \neq y_j \end{cases}$$

4.2 矩阵链乘法

给定 $n$ 个矩阵的链 $<A_1, A_2, …, A_n>$，矩阵 $A_i$ 的维度为 $p_{i-1} \times p_i$，求完全括号化方案，使得计算乘积所需的标量乘法次数最少。

状态转移方程：

$$m[i][j] = \min_{i \leq k < j}{m[i][k] + m[k+1][j] + p_{i-1}p_kp_j}$$

其中 $m[i][j]$ 表示计算矩阵链 $A_i…A_j$ 所需的最少乘法次数。