卡特兰数递归与递推
2021/7/3 6:22:42
本文主要是介绍卡特兰数递归与递推,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1/500
卡特兰数简单来说就是对于一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?下面给出一道较小数据例题并对其分析.
题目
解法一: 递归
递归的思路考虑的是当前状态可以变为哪种状态,并找到递归终点再次进行回溯,下面我们分析数字的三种状态
- 在队列中
- 在栈中
- 出栈
对于状态1有一种操作入栈变为状态2,对于状态2可以选择出栈变为状态3,三种状态有且存在一种变化1->2->3
考虑到数据范围采用普通递归可能会超时,这里使用记忆化搜索用二维矩阵f[i][j]抽象为队列中数的个数为i,栈中数的个数为j的方案数.
那么对于f[i][j]这个状态可以变为
1.将状态1变为状态2,此时队列中有i-1个数栈中有j+1个数
2.当栈中有元素时(j>1)有状态2变为状态3即为选择一个数字出栈此时队列中有i个数,栈中有j-1个数
if(j>=1)f[i][j]+=dfs(i,j-1) f[i][j]+=dfs(i-1,j+1)
当i=0,即为队列中所有数都入栈有且仅有一种出栈方式``
给出AC代码
#include<iostream> using namespace std; int n; long long ans; long long f[20][20]; long long dfs(int i,int j) { if (f[i][j])return f[i][j]; if (i == 0)return 1; if (j > 0)f[i][j] += dfs(i, j - 1); f[i][j] += dfs(i - 1, j + 1); if (j > 0)f[i][j] += dfs(i, j - 1); return f[i][j]; } int main() { cin >> n; cout<<dfs(n, 0); return 0; }
解法二:递推
递推与递归想法截然相反,但又相似,我们需要考虑的是当前状态是由哪几种状态变化而来的,以及初始可确定的条件是哪些
同样关键的一步是用二维矩阵来表示方案数f[i][j]其中i表示栈中数的个数表示出栈数的个数
对于f[i][j]
1.由f[i][j-1]出栈一个数得到(状态2->3)(i-j>0)
2.由 f[i-1][j]入栈一个数得到(状态1->2)
#include<iostream> using namespace std; int n; long long ans; long long f[20][20]; int main() { cin >> n; for (int i = 0; i <= n; i++) { f[0][i] = 1; } for(int i=1;i<=n;i++) for (int j = i; j <= n; j++) { if (i == j)f[i][j] = f[i - 1][j]; else f[i][j] = f[i - 1][j] + f[i][j - 1]; } cout << f[n][n]; return 0; }
递归递推区别
这里讨论一下两种矩阵f[i][j]对于i和j意义为何有不同,我们来回顾一下两种算法中的i,j.
递归:二维矩阵f[i][j]来表示队列中数的个数为i,栈中数的个数为j的方案数.
递推:二维矩阵来表示方案数f[i][j]其中i表示栈中数的个数,j表示出栈数的个数
参数意义的不同与两种算法的思路有关,我们上面提到,递归考虑的是当前状态该如何变化到下一中状态,我们分析出对于每一个数有1->2->3这种唯一变化,将其拆分为1->2,2>3 两种情况所以对于递归我们应该使用的是状态1,与状态2 来进行变化,而递推则使用已确定的状态1与转态2,所以参数下标应该使用状态2与状态3.
对于该题如果数据较大的情况我们也可以使用卡特兰数公式,本文主要讲解递推与递归两种方法思想,给出链接供大家参考.
卡特兰数的证明与拓展
这篇关于卡特兰数递归与递推的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)