「算法小记」-2：矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】（C++ ）

程序员洲洲

发布于 2024-06-07 14:04:24

710

发布于 2024-06-07 14:04:24

一、题目描述

题目描述：设 A1, A2, …, An 为连续相乘的矩阵序列，矩阵相乘满足乘法结合律，那么一共有多少种相乘的方案？比如 A1, A2, A3, A4 ，通过加括号来体现乘顺序，有 5 种方案： ((A1A2)A3)A4 (A1A2)(A3A4) A1(A2(A3A4)) (A1(A2A3))A4 A1((A2A3)A4) 输入：每组数据给出 1 ≤ n ≤ 30。输出： n 个矩阵的矩阵链相乘方案数。输入5，则输出14。输入10，则输出4862。

解法一：记忆化搜索（区间DP）

#include <iostream>
using namespace std;

long long dp[35][35], n;
long long  dfs(int l, int r) {
	if (l >= r) return 1;
	if (dp[l][r]) return dp[l][r];
	for (int mid = l; mid < r; mid++) {
		dp[l][r] += dfs(l, mid) * dfs(mid + 1, r);
	}
	return dp[l][r];
}
int main() {
	while (cin >> n) {
		dfs(1, n);
		cout << dp[1][n] << endl;
	}
	return 0;
}

如果说简单的理解这个算法，我们可以打一段输出来检测每一次处理的dp数组的具体数值。

也就是说，当n=4时，可以把问题看成：

14 = 11 * 24 + 12 * 34 + 13 * 44。

注意这是一个非常重要的点，有助于我们理解。

用dp[i][j]表示区间[i,j]的乘法方案数量，真正的核心点是考虑乘法发生在哪个划分点（切点）。然后不断的去更新这个数量并进行相加。

具体过程可以看成如下：

1. 初始化dp数组：
   - 创建一个二维数组dp[35][35]，并将所有元素初始化为0。

2. 调用dfs(1, 5)：
   - 进入dfs函数，参数l=1，r=5。

3. 判断基本情况：
   - l=1 小于 r=5，继续执行。

4. 判断是否已计算过：
   - dp[1][5]的值为0（初始值），继续执行。

5. 循环遍历分割点：
   - 初始化mid=l=1。
   - 进入循环：
     - mid=1，计算dp[1][5] += dfs(1, 1) * dfs(2, 5)。

       - 计算dfs(1, 1)：
         - 进入dfs函数，参数l=1，r=1。
         - 判断基本情况：l=1 等于 r=1，返回1。
         - 返回结果1。

       - 计算dfs(2, 5)：
         - 进入dfs函数，参数l=2，r=5。
         - 判断基本情况：l=2 小于 r=5，继续执行。
         - 判断是否已计算过：dp[2][5]的值为0（初始值），继续执行。
         - 循环遍历分割点：
           - 初始化mid=2。
           - 进入循环：
             - mid=2，计算dp[2][5] += dfs(2, 2) * dfs(3, 5)。

               - 计算dfs(2, 2)：
                 - 进入dfs函数，参数l=2，r=2。
                 - 判断基本情况：l=2 等于 r=2，返回1。
                 - 返回结果1。

               - 计算dfs(3, 5)：
                 - 进入dfs函数，参数l=3，r=5。
                 - 判断基本情况：l=3 小于 r=5，继续执行。
                 - 判断是否已计算过：dp[3][5]的值为0（初始值），继续执行。
                 - 循环遍历分割点：
                   - 初始化mid=3。
                   - 进入循环：
                     - mid=3，计算dp[3][5] += dfs(3, 3) * dfs(4, 5)。

                       - 计算dfs(3, 3)：
                         - 进入dfs函数，参数l=3，r=3。
                         - 判断基本情况：l=3 等于 r=3，返回1。
                         - 返回结果1。

                       - 计算dfs(4, 5)：
                         - 进入dfs函数，参数l=4，r=5。
                         - 判断基本情况：l=4 小于 r=5，继续执行。
                         - 判断是否已计算过：dp[4][5]的值为0（初始值），继续执行。
                         - 循环遍历分割点：
                           - 初始化mid=4。
                           - 进入循环：
                             - mid=4，计算dp[4][5] += dfs(4, 4) * dfs(5, 5)。

                               - 计算dfs(4, 4)：
                                 - 进入dfs函数，参数l=4，r=4。
                                 - 判断基本情况：l=4 等于 r=4，返回1。
                                 - 返回结果1。

                               - 计算dfs(5, 5)：
                                 - 进入dfs函数，

解法二：

#include <iostream>
using namespace std;
long long cishu(int n) {
    long long dp[100][100] = {0};
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 1;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = 0;

            for (int k = i; k < j; k++) {
            	//用dp[i][j] 表示区间[i,j]的乘法方案数，考虑最后一次乘法发生在哪里来划分子问题 
                dp[i][j] = dp[i][j] + (dp[i][k] * dp[k + 1][j]);
            }
        }
    }
    return dp[1][n];
}
int main() {
    int n;
    while(cin >> n){
        long long num = cishu(n);
        cout << num << endl;
    }
}