【数据结构与算法】进出栈方案数问题
2021/12/11 22:21:11
本文主要是介绍【数据结构与算法】进出栈方案数问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
进出栈方案数问题
让n个数字依次进栈,求不同的出栈序列的种类个数。
首先可以对问题进行一个转化,脱去数字本身的特性,单纯将出栈序列的序列看成是由进栈和出栈两种操作来构成的序列,其中我们可以令1代表入栈,0代表出栈。
而当出栈序列是非法的时候,就是在说栈为空时,仍然进行出栈操作,换成01串进行理解,也就是说,在整个01串中,存在某一个位置,且这个位置前面的操作0的个数大于1的个数,即说明这是非法的。
那么,我们要求出所有可行的方案,我们可以换一个角度。
合法方案数 = 总方案数 - 非法方案数
总方案数 = 给你2n个位置,先填入n个1,其他空余位置补上0 = \(C_{2n}^{n}\)
在计算非法方案数,我们可以稍微做一下转换。
(注意这里都是非法的,无论怎么转换的话)假设定在某个位置,这个位置前有p个1,p+1个0, 那么在这个位置后有n-p个1,n-(p+1)个0,在这里,我们可以稍微做一个转换,在这个位置后有n-p个"0",n-(p+1)个"1",所以此时2n个位置共有n+1个"0",n-1个"1"。
所以非法的方案数为\(C_{2n}^{n-1}\)
所以合法的方案数 = \(C_{2n}^{n}-C_{2n}^{n-1}\)
这篇关于【数据结构与算法】进出栈方案数问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现