字符串加括号问题（矩阵乘法组合问题）C++

浅浅的花香味﹌ 2022-05-10 05:52 72阅读 0赞

## 矩阵乘法加括号问题 ##

给定一个长度的字符串，很明显是可以加括号(矩阵乘法的结合律)  
所以，一共有多少种加括号的方式呢?

给出了计算总共有多少这样组合  
例如：  
下面这个串，输入的长度为4。

ABCD

所有的加括号的可能就是

A(B(CD))
    A((BC)D)
    (AB)(CD)
    (A(BC))D
    ((AB)C)D

所以说，输出的结果是5.

### 递归版本 ###

#include <iostream>
    using namespace std;
    int f(int len);
    int main() { 
    	int n;
    	while (cin >> n && n) { 
    		cout << f(n) << endl;
    	}
    }
    
    int f(int len) { 
    	if (len == 1) return 1;
    	int sum = 0;
    	for (int i = 1; i < len; ++i) { 
    		sum += f(i) * f(len - i);
    	}
    	return sum;
    }

**输出结果：**  
在计算到21的时候就会出现问题了,不过估计是因为int整数型不够放的原因。

1
    1
    2
    1
    3
    2
    4
    5
    6
    42
    7
    132
    8
    429
    9
    1430
    10
    4862
    11
    16796
    12
    58786
    13
    208012
    14
    742900
    15
    2674440
    16
    9694845
    17
    35357670
    18
    129644790
    19
    477638700
    20
    1767263190
    21
    -2025814172

进行递归转递推的修改。速度提高了非常多倍。

#include <iostream>
    using namespace std;
    int *f;
    const int MAXSIZE = 1000;
    void cal(int begin, int end);
    int main() { 
    	int n, everN_MAX=0;
    	f = new int[MAXSIZE];
    	while (cin >> n && n) { 
    		if (n > everN_MAX) {  cal(everN_MAX, n); }
    		cout << f[n] << endl;
    	}
    	delete[] f;
    }
    
    void cal(int begin, int end) { 
    	int i, j;
    	for (i = begin; i <= end; i++) { 
    		if (i == 1) f[i] = 1;
    		else { 
    			f[i] = 0;
    			for (j = 1; j < i; ++j) f[i] += f[j] * f[i - j];
    		}
    	}
    }

这个就简单多了，输出的结果试了试。

1
    1
    2
    1
    3
    2
    4
    5
    5
    14
    6
    42
    7
    132
    8
    429
    9
    1430
    10
    4862
    11
    16796
    12
    58786
    13
    208012
    14
    742900
    15
    2674440
    16
    9694845
    17
    35357670
    18
    129644790
    19
    477638700
    20
    1767263190
    21
    -2025814172