在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,问有多少种拆分方案。 例如五边形有如下五种拆分方案。
第一行输入一个整数n(3<=n<=32)。
输出一个数表示划分方案的总数。
5
5
3<=n<=32
1 #include<iostream>
2 using namespace std;
3 long long int f[1001];
4 int main()
5 {
6 int n;
7 f[2]=1;
8 f[3]=1;
9 cin>>n;
10 //n=n+2;
11 for(int i=4;i<=n;i++)
12 {
13 for(int j=2;j<=n-1;j++)
14 {
15 f[i]=f[j]*f[i-j+1]+f[i];
16 }
17 }
18 cout<<f[n];
19 return 0;
20 }