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

Difficulty
Hard
Tags
动态规划
URL
https://leetcode-cn.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/
Star
给你一个数组 nums 表示 1 到 n 的一个排列。我们按照元素在 nums 中的顺序依次插入一个初始为空的二叉查找树（BST）。请你统计将 nums 重新排序后，统计满足如下条件的方案数：重排后得到的二叉查找树与 nums 原本数字顺序得到的二叉查找树相同。
比方说，给你 nums = [2,1,3]，我们得到一棵 2 为根，1 为左孩子，3 为右孩子的树。数组 [2,3,1] 也能得到相同的 BST，但 [3,2,1] 会得到一棵不同的 BST 。
请你返回重排 nums 后，与原数组 nums 得到相同二叉查找树的方案数。
由于答案可能会很大，请将结果对 10^9 + 7 取余数。
示例 1：
notion imagenotion image
输入：nums = [2,1,3]
输出：1
解释：我们将 nums 重排， [2,3,1] 能得到相同的 BST 。没有其他得到相同 BST 的方案了。
示例 2：
notion imagenotion image
输入：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]
示例 3：
notion imagenotion image
输入：nums = [1,2,3]
输出：0
解释：没有别的排列顺序能得到相同的 BST 。
示例 4：
notion imagenotion image
输入：nums = [3,1,2,5,4,6]
输出：19
示例 5：
输出：216212978
解释：得到相同 BST 的方案数是 3216212999。将它对 10^9 + 7 取余后得到 216212978。
提示：
  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= nums.length
  • nums 中所有数 互不相同 。

动态规划

思路
怎么理解题目呢？
将数组中的数字插入到bst中还要保持和原来的bst一样，
在当前层的数组nums， 以nums[0]为轴（因为nums[0]一定是当前子树的根节点），将其分成两部分。记做left和right。left有组合的方式，right中也有组合的方式，进行结合以后，由于插入顺序只要满足left和right中各自的相对顺序即可，插入left和插入right中的元素互不影响。所以从l-1个位置中，选出left.size()个位置放left的元素，其余放right的元素。
所以有如下答案：
左子树的组合个数 * 右子树的组合个数 * 数组混合组合个数。
左子树 右子树的个数很好理解。
数组混合的个数：相当于是 在 len(left) + len(right) 中找 len(left)个坑，将left中的元素放进去，至于为什么是组合，因为要保证 left中元素的相对位置。
次数数组为什么可以混合呢？
因为选好根节点之后，即选定nums[0]之后，剩下的元素一半在左边，一半在右边，只要左右两边的元素保证各自边的相对顺序即可，至于左边的元素中混入了右边的元素根本没有影响。
题解
from typing import List
from math import comb

MOD = 10 ** 9 + 7
# 子树1排序数*子树2排序数*组内保持顺序合并数组的方式comb
class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        def countWays(nums: List[int]) -> int:
            if len(nums) <= 2:
                return 1
            left = [v for v in nums if v < nums[0]]
            right = [v for v in nums if v > nums[0]]
						# countWays(left) * countWays(right) 分别为左子树 右子树的 各自的组合方式
						# comb(len(left) + len(right), len(left)) 计算的是： 
						# 当前这一层的 nums中的数字的前后组合方式，为什么是组合呢？因为要保证left，和right本身的相对位置不变.
						# 所以相当于在 len(left) + len(right) 中找 len(left)个坑，将left中的元素放进去 
            return comb(len(left) + len(right), len(left)) * countWays(left) * countWays(right)

        return (countWays(nums) - 1) % MOD
使用自己实现的组合计算公式
MOD = 10 ** 9 + 7
class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        self.memo = [[None] * (len(nums)+1) for _ in range(len(nums)+1)]
        return (self.countWays(nums) - 1) % MOD

    def countWays(self, nums: List[int]) -> int:
            if len(nums) <= 2:
                return 1
            left = [v for v in nums if v < nums[0]]
            right = [v for v in nums if v > nums[0]]
            return self.nCk(len(left)+len(right), len(left)) * self.countWays(left) * self.countWays(right)

    def nCk(self, n, k):
        if n == k or k == 0:
            return 1

        if self.memo[n][k] is None:
            if self.memo[n][n-k]:
                self.memo[n][k] = self.memo[n][n-k]
            else:
                self.memo[n][k] = self.nCk(n-1, k-1) + self.nCk(n-1, k)
                self.memo[n][n-k] = self.memo[n][k]
                
        return self.memo[n][k]