LeetCode 1569. 将子数组重新排序得到同一个二叉查找树的方案数（DP）

输入：nums = [2,1,3]
输出：1
解释：我们将 nums 重排， [2,3,1] 能得到相同的 BST 。
没有其他得到相同 BST 的方案了。

输入：nums = [3,4,5,1,2]
输出：5
解释：下面 5 个数组会得到相同的 BST：
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]

输入：nums = [1,2,3]
输出：0
解释：没有别的排列顺序能得到相同的 BST 。

输入：nums = [3,1,2,5,4,6]
输出：19

示例  5：
输入：nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
输出：216212978
解释：得到相同 BST 的方案数是 3216212999。
将它对 10^9 + 7 取余后得到 216212978。
 
提示：
1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
nums 中所有数 互不相同 。

class Solution {
	vector<vector<int>> C;
	int mod = 1e9+7;
public:
    int numOfWays(vector<int>& nums) {
    	int n = nums.size();
    	C = vector<vector<int>> (n+1, vector<int>(n+1, 0));
    	C[1][0] = 1, C[1][1] = 1;
    	// DP 求解组合数
    	for(int i = 2, j; i <= n; ++i)
    	{
    		for(j = 0; j <= i; ++j)
    		{
    			if(j==0 || j==i)
    				C[i][j] = 1;
    			else
    			{
    				C[i][j] = (C[i-1][j-1] + C[i-1][j])%mod;
    			}
    		}
    	}
    	return (dfs(nums)-1)%mod;
    }
    long long dfs(vector<int> &nums)
    {
    	if(nums.size() <= 1)
    		return 1;
    	int root = nums[0], n = nums.size();
    	vector<int> l, r;
    	for(int num : nums)
    	{
    		if(num < root)
    			l.push_back(num);
    		else if(num > root)
    			r.push_back(num);
    	}
    	long long nL = dfs(l), nR = dfs(r);
    	return (((C[n-1][l.size()]*nL)%mod)*nR)%mod;
    }
};