C3-C

C3-C 矩阵连乘

题目描述

$n$个矩阵连乘，求有多少种乘法$P(n)$？

输入

一个正整数$n$，表示矩阵个数，$1≤n≤35$。

输出

$1∼n $个矩阵连乘，分别有多少种乘法。

题目分析

将$n$个矩阵分为两部分$i,n-i$则：

$P(n)=\sum P(i)*P(n-i)$

示例代码

dp[1]=1;
dp[2]=1;
for (int i = 3; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i] += dp[j] * dp[i - j];
        }
    }