问题

给出一个长度为 $n$ 的序列 $P$ 表示 $n-1$ 个矩阵
其中 $P_i,P_i+1$ 分别表示第 $i$ 个矩阵的行和列
将 $n$ 个矩阵按顺序相乘，最少需要做多少次乘法

解析

对于行列分别为 $a,b$ 和 $b,c$ 的两个矩阵相乘，共需要 $a*b*c$ 次乘法
同时对于矩阵乘法，满足结合律但不满***换律，即 $abc=a(bc)\ne acb$
例如：对于序列 $[10,100,5,50]$ 表示矩阵 $<10,100>\times<100,5>\times<5,50>$

按照原顺序，总运算次数为 $10\times100\times5+10\times5\times50=7500$
先对后两项做乘法，总运算次数为 $100\times5\times50+10\times100\times50=75000$

显然不同的结合顺序会使总运算次数产生很大区别
做法：
我们考虑用动态规划的方法来解决这个问题
令 $dp[l][r]$ 表示第 $l$ 到 $r$ 各矩阵按一定顺序相乘的最小乘法次数
则 $dp[l][r]=\min\{dp[l][k]+dp[k+1][r]+P[l]*P[k+1]*P[r+1]\},l \le k \le r$

证明满足最优化法则
- 已知 $dp[l][r]$ 是当前子问题的最优答案
- 假设 $dp[l][k]$ 不是最优的子问题答案，即存在 $dp'[l][k]\lt dp[l][k]$
- 那么 $dp'[l][k]+dp[k+1][r]+P[l]*P[k+1]*P[r+1]\lt dp[l][k]+dp[k+1][r]+P[l]*P[k+1]*P[r+1]$
- 也就是存在更优的 $dp[l][r]$ ，这与之前的假设相矛盾，得证

设计

 for (int i = 1; i <= n - 1; ++i)
        dp[i][i] = 0, s[i][i] = i;
    for (int len = 2; len <= n - 1; ++len)
    {
        for (int l = 1, r; l + len - 1 <= n - 1; ++l)
        {
            r = l + len - 1;
            int cur = a[l] * b[r];
            for (int k = l; k < r; ++k)
            {
                if (dp[l][k] + dp[k + 1][r] + cur * b[k] < dp[l][r])
                {
                    s[l][r] = k;
                    dp[l][r] = dp[l][k] + dp[k + 1][r] + cur * b[k];
                }
            }
        }
    }

分析

对于上述算法，共有3重循环，其中第一重 $n$ 次，第二重 $n-len$ 次，第三重 $len$ 次
总复杂度为 $\sum_{i=1}^n\sum_{j=1}^{n-i}i=\sum_{i=1}^nn*i-i*i=n*\frac{n(n+1)}{2}-\frac{n(n+1)(2n+1)}{6}=\frac{n^3+n}{6}\sim O(n^3)$

源代码

传送门

算法课-矩阵链乘法

问题

解析

设计

分析

源代码