欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P1044 栈(卡特兰数)

程序员文章站 2022-07-13 11:51:24
...

P1044 栈(卡特兰数)
P1044 栈(卡特兰数)
P1044 栈(卡特兰数)
思路:卡特兰数和动态规划。
卡特兰数:一个栈(无穷大)的进栈序列为1,2,3,…n,问有多少个不同的出栈序列。
设f(n)为序列个数是n的出栈序列种数。首先设最后出栈的元素为k,(k取不同值是相互独立的,所以所有的k的出栈情况可用加法原则)。由于k最后出栈,所以比k小的元素都已经出栈了,此处有f(k-1)种,而之后比k大的入栈,且在k之前出栈,此处有f(n-k)种方式。因为二者相互独立,所以总共有f(k-1)*f(n-k)种。而k可以选择1到n,再根据加法原则将不同值的序列总数相加,总序列种数为:f(n)=f(0)*f(n-1)+f(1)*f(n-2)+…+f(n-1)*f(0).所以,得到递推式:
设h(n)为卡特兰数的第n+1项,令h(0)=1,h(1)=1,递推式为:
h(n)=h(0)*h(n-1)+h(1)h(n-2)+…+h(n-1)h(0).(n>=2)
另类递推式:h(n)=h(n-1)
(4
n-2)/(n+1)
P1044 栈(卡特兰数)
f(0) = 1;

f(1) = 1;

f(2) = f(0)*f(1) + f(1)*f(0);

f(3) = f(0)*f(2) + f(1)*f(1) * f(2)*f(0);

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + …+ f(n-2)*f(1) + f(n-1)*f(0)


```cpp
#include<iostream>
using namespace std;
int main()
{
    int a[20]={0};
    int n;
    cin>>n;
    a[0]=1;
    a[1]=1;
    for(int i=2;i<=n;i++)
        for(int j=0;j<i;j++)
        a[i]=a[i]+a[j]*a[i-1-j];
    cout<<a[n]<<endl;
    return 0;
}


相关标签: 知识点