C++实现求解矩阵连乘时最少的乘法次数【动态规划】

思路：

我们采用的是自底向上的解决方法。

下图 $m[i][j]$ （也就是代码中的$dp[i][j]$）代表了矩阵 $[i,...,j]$ 相乘时最少的乘法次数。

首先我们解决主对角线上的元素，因为自己不用与自己相乘，所以对角线上的元素（也就是 $m[k][k]$ ）都为 $0$ 。

接下来，我们按照从中间都右上角的顺序解决每一条次对角线上的子问题。注意，每一个子问题都应该基于其他子问题来解决（有点类似于分治法）。

例如 $m[1][3]$ 这个子问题，我们可以通过
$$min(m[1][1]+m[2][3]+r_1\ast c_1\ast c_3,m[1][2]+m[3][3]+r_1\ast c_2\ast c_3)$$
来求解。

使用动态规划方法时一定要疯狂暗示自己子问题已经得到正确的求解！

源代码：

//
// main.cpp
// MatrixMultiplication
//
// Created by 胡昱 on 2021/11/10.
//

#include <iostream>
using namespace std;

// 存储矩阵信息
struct Matrix{
    
    int r;
    int c;
};

int main(int argc, const char * argv[]) {
    
    // 共m个问题
    int m;
    cin >> m;
    while((m--) > 0) {
    
        // 初始化矩阵数组以及动态规划数组
        // dp[i][j]代表了矩阵[i, ..., j]相乘时最少的乘法次数
        int n;
        cin >> n;
        Matrix* ms = new Matrix[n];
        int** dp = new int*[n];
        for(int i = 0; i < n; ++i) {
    
            ms[i] = Matrix();
            cin >> ms[i].r >> ms[i].c;
            dp[i] = new int[n];
            dp[i][i] = 0;   // 矩阵不需要和自己相乘（也就是主对角线上的元素都为0）
        }
        
        // 动态规划解决问题（也就是沿着主对角线的平行线解决子问题）
        for(int bias = 1; bias < n; ++bias) {
    
            for(int k = 0; k < n - bias; ++k) {
    
                // 通过设置断点，逐个求解dp[k][k + bias]
                dp[k][k + bias] = 2147483647;   // INT_MAX
                for(int ki = k; ki < k + bias; ++ki) {
    
                    dp[k][k + bias] = min(dp[k][k + bias],
                                          dp[k][ki] + dp[ki + 1][k + bias] + ms[k].r * ms[ki].c * ms[k + bias].c);
                }
            }
        }
        
        // 输出答案并释放资源
        cout << dp[0][n - 1] <<endl;
        for(int i = 0; i < n; ++i) {
    
            delete [] dp[i];
        }
        delete [] dp;
    }
    return 0;
}