做这道题用到的:https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/description/
求两个数组归并后可能产生多少种组合,要求归并后两个数组元素仍有保持原数组中的顺序
其实是个很简单的问题,是我开始想复杂了
假设两个数组长度分别为m和n,则归并后长度为m+n,则问题可以转换为从m+n个索引里面挑选出m个(或n个)索引有多少种方式
其实就是 \( C_{m+n}^m = C_{m+n}^n = \frac {(m+n)!}{m!×n!} \)
组合(Combination)公式为
\[ C_n^k = \frac {n!}{k!×(n-k)!} \]
在python中可以用 math.comb(n, k)
进行计算
排列(Arrangement,从n个元素中选出k个元素并排序)公式为
\[ A_n^k = \frac {k!}{(n-k)!} \]
python中使用 math.perm(n, k)
进行计算