【洛谷】P1044 栈
程序员文章站
2022-07-13 11:51:54
...
【洛谷】P1044 栈
卡特兰数数学原理:
算法分析:
- 假设[1…n]有序序列经过一番压栈出栈操作后,数字k是最后一个出栈元素
- 数字k将整个序列分成了两部分,[1…k-1]均先于k进行操作,[k+1…n]均晚于k进行操作
- 整个过程可以描述为:在k压栈之前[1…k-1]个元素已经全部压栈并出栈完毕,然后k压栈,存于栈底,之后[k+1…n]个元素同样进行压栈并全部出栈,剩下了k依然留在栈底,最后k才出栈。
- 如果记i个元素最终获得的序列为f(i)种,则前
[1...k-1]
个元素为f(k-1)
种,后[k+1...n]
元素为f(n-k)
种,因为前后两部分元素压栈出栈相互独立,可以直接使用乘法原理,则f(k-1)*f(n-k)
f(k-1)*f(n-k)
表示当第k个元素最后出栈时,共有f(k-1)*f(n-k)
种可能- 当第 1 个元素最后出栈时,共有
f(0)*f(n-1)
种 - 当第 2 个元素最后出栈时,共有
f(1)*f(n-2)
种 - 当第 3 个元素最后出栈时,共有
f(2)*f(n-3)
种 - …
- 当第n-1个元素最后出栈时,共有
f(n-2)*f(1)
种 - 当第 n 个元素最后出栈时,共有
f(n-1)*f(0)
种 - 因此,n个元素的序列,共有
f(n)=f(0)*f(n-1) + f(1)*f(n-2) + ....+ f(n-2)*f(1) + f(n-1)*f(0)
种可能
总结出递推公式:
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)
算法设计:
使用数组f[N]存储n个元素的序列压栈出栈操作结果种数,f[0] = 1, f[1] = 1, 然后利用递推公式,循环求出其他值
代码实现:
int main()
{
int n;
int f[20] = {0};
f[0] = 1;
f[1] = 1;
scanf("%d", &n);
for(int i=2; i<=n; i++)
for(int j=0; j<i; j++)
f[i] += f[j]*f[i-1-j];
printf("%d", f[n]);
return 0;
}
上一篇: LintCode 391. 数飞机 Python算法
下一篇: P1044 栈(洛谷)