动态规划高级应用：典型问题

今天我们来聊聊动态规划的三个经典问题：矩阵连乘、最优二叉搜索树、凸多边形最优三角剖分。说实话，这三个问题我在工作中都遇到过它们的变体。比如矩阵连乘，我在做深度学习框架的算子优化时就碰到过类似的计算顺序问题。

这三个问题有个共同点——它们都是区间DP的典型代表。什么意思呢？就是在一个连续的区间上做决策，把大区间拆成小区间，最后合并出最优解。

核心思想：最优子结构 + 区间划分 + 状态转移

1. 矩阵连乘问题

先说说矩阵连乘。给定一堆矩阵，你要决定先乘哪两个，再乘哪两个……不同的顺序，计算量天差地别。

举个例子：A(10×100)、B(100×5)、C(5×50)。

  • (AB)C：10×100×5 + 10×5×50 = 5000 + 2500 = 7500次乘法
  • A(BC)：100×5×50 + 10×100×50 = 25000 + 50000 = 75000次乘法

你看，差了整整10倍！

我在项目中遇到过类似场景——做矩阵运算库时，用户传了一串矩阵，我得自动找出最优计算顺序。嗯，这就是矩阵连乘的用武之地。

状态定义

定义 dp[i][j] 表示从第 i 个矩阵乘到第 j 个矩阵的最小乘法次数。

状态转移方程

dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])  (i ≤ k < j)

其中 p 数组存储矩阵的维度：矩阵 Ai 的维度是 p[i-1]×p[i]。

代码实现

int matrixChainOrder(int p[], int n) {
    int dp[n][n];
    // 初始化：单个矩阵不需要乘法
    for (int i = 1; i < n; i++)
        dp[i][i] = 0;
    
    // L是区间长度
    for (int L = 2; L < n; L++) {
        for (int i = 1; i < n - L + 1; i++) {
            int j = i + L - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j];
                if (cost < dp[i][j])
                    dp[i][j] = cost;
            }
        }
    }
    return dp[1][n-1];
}

小技巧：我习惯用L表示区间长度，从2开始枚举。这样代码逻辑清晰，不容易出错。

2. 最优二叉搜索树

这个问题很有意思。给定一组关键字和它们的搜索概率，要构造一棵二叉搜索树，使得平均查找代价最小。

你想想看，高频词应该放在靠近根的位置，低频词放得深一点。但问题来了——BST还有中序遍历有序的约束，不能随便排。

状态定义

定义 dp[i][j] 表示关键字 ki 到 kj 构成的最优BST的代价。

状态转移方程

dp[i][j] = min(dp[i][k-1] + dp[k+1][j] + sum(p[i..j]))  (i ≤ k ≤ j)

这里的 sum(p[i..j]) 是 ki 到 kj 的概率之和。为什么要加这个？因为把 k 提成根后，左右子树所有节点的深度都增加了1，代价自然要加上去。

代码实现

double optimalBST(double p[], int n) {
    double dp[n+2][n+2] = {0};
    double sum[n+2][n+2] = {0};
    
    // 预处理概率和
    for (int i = 1; i <= n; i++) {
        sum[i][i] = p[i];
        for (int j = i+1; j <= n; j++)
            sum[i][j] = sum[i][j-1] + p[j];
    }
    
    for (int L = 1; L <= n; L++) {
        for (int i = 1; i <= n - L + 1; i++) {
            int j = i + L - 1;
            dp[i][j] = DBL_MAX;
            for (int k = i; k <= j; k++) {
                double cost = dp[i][k-1] + dp[k+1][j] + sum[i][j];
                if (cost < dp[i][j])
                    dp[i][j] = cost;
            }
        }
    }
    return dp[1][n];
}

注意：边界处理要小心。当 k=i 时，左子树为空；当 k=j 时，右子树为空。我刚开始写的时候忘了处理 dp[i][i-1] 和 dp[j+1][j] 的情况，结果数组越界了。

3. 凸多边形最优三角剖分

这个问题，说白了就是给一个凸多边形，用不相交的对角线把它切成三角形，要求所有三角形权值和最小。

权值怎么定义？通常是三角形三个顶点构成的某种函数，比如周长、面积、或者顶点权值之和。

状态定义

定义 dp[i][j] 表示从顶点 vi 到 vj 构成的子多边形的最优三角剖分代价。

状态转移方程

dp[i][j] = min(dp[i][k] + dp[k][j] + w(vi, vk, vj))  (i < k < j)

这里的 w(vi, vk, vj) 是三角形 (vi, vk, vj) 的权值。

代码实现

double minTriangulation(int n, double (*weight)(int, int, int)) {
    double dp[n][n];
    // 初始化：相邻顶点不能构成三角形
    for (int i = 0; i < n; i++)
        dp[i][i+1] = 0;
    
    for (int L = 2; L < n; L++) {
        for (int i = 0; i < n - L; i++) {
            int j = i + L;
            dp[i][j] = DBL_MAX;
            for (int k = i+1; k < j; k++) {
                double cost = dp[i][k] + dp[k][j] + weight(i, k, j);
                if (cost < dp[i][j])
                    dp[i][j] = cost;
            }
        }
    }
    return dp[0][n-1];
}

三个问题的统一框架：

  1. 枚举区间长度 L
  2. 枚举区间起点 i
  3. 计算区间终点 j = i + L - 1
  4. 枚举分割点 k
  5. 根据状态转移方程更新 dp[i][j]

知识体系总览

下面这张图帮你理清这三个问题的关系：

动态规划高级应用：区间DP三大经典问题 区间DP 矩阵连乘 最优二叉搜索树 凸多边形三角剖分 特征 乘法次数最小化 dp[i][j] = min(dp[i][k] + dp[k+1][j] + ...) 特征 查找代价最小化 dp[i][j] = min(dp[i][k-1] + dp[k+1][j] + sum) 特征 三角形权值和最小 dp[i][j] = min(dp[i][k] + dp[k][j] + w) 共同框架：枚举区间长度 → 枚举起点 → 枚举分割点 → 状态转移

避坑指南

我曾经在实现最优BST时犯过一个低级错误——把概率和 sum[i][j] 加在了错误的位置。你想想看，每次把 k 提成根，左右子树的深度都增加了1，所以 sum[i][j] 必须加在 min 外面，而不是里面。

还有一点：这三个问题的时间复杂度都是 O(n³)。n 在 100 以内还好，超过 500 就要考虑优化了。我在项目中用过四边形不等式优化，能把 O(n³) 降到 O(n²)，但那是另一个话题了。

我的建议：先理解矩阵连乘，它是最直观的。然后看最优BST，理解概率和为什么要加。最后看凸多边形，你会发现它和矩阵连乘几乎一模一样——只是权值函数不同。

好了，这三个问题就讲到这里。代码我都跑过，没问题。你可以在自己的机器上试试，改改参数看看效果。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →