c++ - 使用笛卡尔积寻找唯一 BST 数量背后的直觉

Question

我正在解决 LeetCode 问题。问题是:

Given n, how many structurally unique BSTs can be generated, that store the values from 1...n? For e.g., for n=3, a total of 5 unique BSTs can be generated as follows:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

最高投票解决方案使用 DP 和以下递归公式:

G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0) 

其中 G(n) 表示可以为 n 生成的唯一 BST 的数量。代码如下:

class Solution {
public:
    int numTrees(int n) {
        vector<int> G(n+1);
        G[0]=G[1]=1;

        for(int i=2; i<=n; i++)
            for(int j=1; j<=i; j++)
                G[i]+=G[j-1]*G[i-j];

        return G[n];
    }
};

虽然我或多或少明白发生了什么，但我不明白为什么我们采用笛卡尔积(而不是更直观的简单加法)。据我了解:

G[i] += G[j-1] * G[i-j];

应该改为:

G[i] += G[j-1] + G[i-j];  //replaced '*' with a '+'

这是因为，我认为 i 作为当前根可能的唯一 BST 的数量应该是其 BST 数量的 sum(?)左子树和右子树。我确实尝试了几个例子，但不知何故，数字在原始解决方案中神奇地成倍增加(使用 *)，最终答案出现在 G[n] 中。

有人可以提供使用笛卡尔积而不是求和的直观解释吗？

注意:原来的问题是here解决方案是here .此外，原始代码是用 Java 编写的，而我已经发布了上面编写的 C++ 变体。

Answer 1

您可以通过数学归纳法，然后将其应用于子问题以获得结果。或者只是检查较小的值，然后选择较高的值。

例如:-

No of nodes      BST representation

1   -->    [1]

2   -->  [2]  [1]
         /     \
        [1]    [2]

3   -->  [1]
           \
           [2]
             \
             [3]

         [2]
         / \
        [1] [3]

          [3]
          /
       [2]
       /
      [1]
4  --> 
        [1]
      /     \
     NUM{}  NUM of keys with 3 val NUM{2,3,4}

      [2]
      /  \
    NUM{1} NUM{3,4}

      [3]
      /  \
    NUM{1,2} NUM{4}

          [4]
         /     \
    NUM{1,2,3}  NUM{}

从第4种情况可以清楚地了解到，我们必须简单地将每棵树中左右子树分组的可能方式的数量相乘。对于给定数量的值，我们必须将它们相加。这就是使用笛卡尔积的原因。

该产品基本上为我们提供了全部真实可能拥有的所有可能顺序。 例如:

G[i] += G[j-1] * G[i-j]; Here j-1 nodes are to the left( we can assume without loss of generality) and i-j nodes to the right sub-tree. And now you can arrange the left sub-tree in G[j-1] ways and similarly for right sub-tree in G[i-j] ways. Now think how many ways can you arrange the original tree which has this left and rigth subtree? It would multiply. Because each combination of left and right subtree will give rise to a unique tree representation.

这也解释了为什么我们定义 G[0]=1 因为它符合我们在这里做事的方式。而且没有值的排列数也是一种排列。所以认为是1。