小编ILi*_*hon的帖子

我正在实现一个函数来计算第 n 个加泰罗尼亚数字。序列的公式如下：

我注意到记忆的解决方案比正常的递归解决方案慢。这是我的代码：

#include <bits/stdc++.h>
using namespace std;


int catalan_number_recursive(int n){
    if (n == 0) return 1;

    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_recursive(i)*catalan_number_recursive(n - 1 - i);
        }

        return ans;
    }
}

int catalan_number_memo(int n, map<int, int> memo){
    memo[0] = memo[1] = 1;


    if (memo.count(n) != 0){
        return memo[n];
    }
    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_memo(i, memo)*catalan_number_memo(n …