卡塔兰数(Catalan Numbers) 是个很神奇的数列. 高中信息学竞赛很喜欢出有关卡塔兰数的问题, 特别是在初赛(笔试)的时候, 经常会有一题真空题就是卡塔兰数的应用.
在组合数学中, 卡塔兰数有着许多应用, 卡塔兰数的前几个数字是:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452
有几个经典的卡塔兰数的应用问题:
- 把一个N边凸多边形切割成N-2个三角形的方案.
- 一个拥有N+1树叶的不同的完全二叉树的数目.
- 在一个NxN的网格里, 从左下往右上走, 每次只能往上和往右, 不能跨过对角线的方案数.
- 产生配对的括号方案数: How to Generate Parentheses using Bruteforce or Depth First Search (Backtracking) Algorithms?
卡塔兰数的数学公式
卡塔兰数可以通过下面的公式来求解:
也可以通过下面的递推公式, 方便编写计算机程序来计算卡塔兰数.
下面还有一个较简单的递归公式, 根据前一个卡塔兰数来计算后一个.
这里有一个简单的实现: How to Compute the Catalan Number?
用递归来计算卡塔兰数
根据上面的第二个公式, 我们可以编写递归来计算卡塔兰数.
1 2 3 4 5 6 7 8 | int64_t catlan(int n) { if (n <= 1) return 1; int res = 0; for (int i = 0; i < n; i ++) { res += catlan(i) * catlan(n - i - 1); } return res; } |
int64_t catlan(int n) { if (n <= 1) return 1; int res = 0; for (int i = 0; i < n; i ++) { res += catlan(i) * catlan(n - i - 1); } return res; }
这个程序效率很低, 复杂度是指数级别的, 因为递归过程中, 展开了很多卡塔兰数都被重复计算了.
动态规化算法计算卡塔兰数(递归+记忆)
我们只要把计算过的卡塔兰数给保存起来 以便下次取用, 递归+这种记忆 Memoization 技巧就是一种动态规化.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | unordered_map<int, int64_t> memo; int64_t catlan(int n) { if (n <= 1) return 1; if (memo.find(n) != memo.end()) { // 已经计算过了, 就直接返回. return memo[n]; } int res = 0; for (int i = 0; i < n; i ++) { res += catlan(i) * catlan(n - i - 1); } memo[n] = res; // 保存该卡塔兰数的值, 以便下次直接用. return res; } |
unordered_map<int, int64_t> memo; int64_t catlan(int n) { if (n <= 1) return 1; if (memo.find(n) != memo.end()) { // 已经计算过了, 就直接返回. return memo[n]; } int res = 0; for (int i = 0; i < n; i ++) { res += catlan(i) * catlan(n - i - 1); } memo[n] = res; // 保存该卡塔兰数的值, 以便下次直接用. return res; }
我们把值保存在一个哈希表里. 存和取的时间复杂度都是常数级别的O(1). 上面计算卡塔兰数的时间复杂度是 O(N^2) 空间复杂度是 线性 O(N).
迭代式的动态规化算法来计算卡塔兰数
我们可以把递归改写成迭代, 这样就省去了调用函数的开销. 我们把卡塔兰数保存在一个vector里. 这种方式是比较高效的. 时间复杂度也是 O(N^2)
1 2 3 4 5 6 7 8 9 10 11 | int catlan(int n) { vector<int64_t> dp(n + 1, 0); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i ++) { for (int j = 0; j < i; ++ j) { dp[i] += dp[j] * dp[i - j - 1]; } } return (int)dp.back(); } |
int catlan(int n) { vector<int64_t> dp(n + 1, 0); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i ++) { for (int j = 0; j < i; ++ j) { dp[i] += dp[j] * dp[i - j - 1]; } } return (int)dp.back(); }
英文: How to Compute the Catalan Numbers using Dynamic Programming Algorithm?
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK