卡塔兰数(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?
loading...
上一篇: 被动收入可遇不可求
下一篇: 英国 stagecoach 表演课真是又贵又费时的课外兴趣班啊
大部分知识还给了老师, 要不是前几年自考了一次, 估计会全换回去.