组合数学中卡塔兰数的动态规化求解方法

卡塔兰数(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?

catalan-numbers-applications

卡塔兰数的数学公式

卡塔兰数可以通过下面的公式来求解:

catalan-numbers-formula

也可以通过下面的递推公式, 方便编写计算机程序来计算卡塔兰数.

catalan-numbers-recurrence-relations

下面还有一个较简单的递归公式, 根据前一个卡塔兰数来计算后一个.

catalan-numbers-recurrence-relations-simple

这里有一个简单的实现: How to Compute the Catalan Number?

用递归来计算卡塔兰数

根据上面的第二个公式, 我们可以编写递归来计算卡塔兰数.

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 技巧就是一种动态规化.

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)

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?