组合数学

卡特兰数

• 卡特兰数: https://oi-wiki.org/math/combinatorics/catalan/

题目	难度
95. 不同的二叉搜索树 II	中等
96. 不同的二叉搜索树	中等
894. 所有可能的真二叉树	中等

96. 不同的二叉搜索树

public class Solution96 {
    public int numTrees(int n) {
        // 状态定义
        // dp[i] 长度为 i 的序列能构成的不同二叉搜索树的个数
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        // 状态转移
        for (int i = 2; i < n + 1; i++) {
            for (int j = 1; j < i + 1; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    // 卡特兰数
    // 时间复杂度 O(n)
    // 空间复杂度 O(1)
    public int numTrees2(int n) {
        // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
        long C = 1;
        for (long i = 0; i < n; i++) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) C;
    }
}

894. 所有可能的真二叉树

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution894 {
    private Map<Integer, List<TreeNode>> memo;

    public List<TreeNode> allPossibleFBT(int n) {
        memo = new HashMap<>();
        return dfs(n);
    }

    private List<TreeNode> dfs(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        List<TreeNode> resList = new ArrayList<>();
        if (n == 1) {
            resList.add(new TreeNode(0));
        } else if (n % 2 == 1) {
            for (int x = 0; x < n; x++) {
                int y = n - 1 - x;
                for (TreeNode left : allPossibleFBT(x)) {
                    for (TreeNode right : allPossibleFBT(y)) {
                        TreeNode root = new TreeNode(0);
                        root.left = left;
                        root.right = right;
                        resList.add(root);
                    }
                }
            }
        }
        memo.put(n, resList);
        return resList;
    }
}

斯特林数

• 斯特林数: https://oi-wiki.org/math/combinatorics/stirling/

题目	难度
1866. 恰有 K 根木棍可以看到的排列数目	困难	第一类斯特林数

1866. 恰有 K 根木棍可以看到的排列数目

public class Solution1866 {
    private static final int MOD = (int) (1e9 + 7);
    private static long[][] TABLES;

    public int rearrangeSticks(int n, int k) {
        if (TABLES == null) {
            TABLES = new long[1001][1001];
            TABLES[0][0] = 1;
            for (int i = 1; i <= 1000; i++) {
                for (int j = 1; j <= i; j++) {
                    TABLES[i][j] = (TABLES[i - 1][j - 1] + (i - 1) * TABLES[i - 1][j]) % MOD;
                }
            }
        }
        return (int) TABLES[n][k];
    }
}

（全文完）