unique_binary_search_trees.cpp

/*
 * @Author: Chacha
 * @Date: 2022-03-08 17:41:30
 * @Last Modified by: Chacha
 * @Last Modified time: 2022-03-09 17:01:50
 */

/**
 * 来源：https://leetcode-cn.com/problems/unique-binary-search-trees/
 *
 * 动态规划 - 不同的二叉搜索树
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 *
 * 二叉搜索树是一个有序树：
 * 1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 * 2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 * 3. 它的左、右子树也分别为二叉排序树
 *
 * 示例1：
 * 输入：n = 2
 * 输出：2
 * 解释：n为2时，可以有2棵搜索树
 *       1   2
 *      /     \
 *     2       1
 *
 *
 * 示例2：
 * 输入：n = 3
 * 输出：5
 * 解释：n为2时，可以有5棵搜索树
 *     1    1                        3        3
 *      \    \          2           /        /
 *       2    3        /  \        2        1
 *      /      \      1    3      /          \
 *     3        2                1            2
 *
 */

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
private:
    /* data */
public:
    int uniqueBinarySearchTree(int n);
};

/**
 * 按照动态规划五部曲来分析：
 * 1. 确定dp数组(dp table)以及下标的含义
 *    dp[i]: 1 到 i 为节点组成的二叉搜索树的个数为 dp[i]。
 * 2. 确定递推公式
 *    从上述示例2可以看出：
 *    1. 当1为根节点的时候，其右子树有两个节点，这两个节点的布局，和 n 为 2 的两棵树的布局是一样；
 *    2. 当2为根节点的时候，其左右子树都只有一个节点，布局和 n 为 1 的时候只有一棵树的布局是一样的；
 *    3. 当3为根节点的时候，其左子树有两个节点，和 n 为 2 的两棵树的布局是一样；
 *    所以，可以得出，dp[3]就是，元素1为头结点搜索树数量 + 元素2为头结点搜索树的数量 + 元素3为头结点的搜索数量。
 *
 *    元素1为根节点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
 *    元素2为根节点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
 *    元素3为根节点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
 *
 *    有0个元素的搜索树数量就是 dp[0]
 *    有1个元素的搜索树数量就是 dp[1]
 *    有2个元素的搜索树数量就是 dp[2]
 *
 *    所以可以推出公式，dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2];
 *    dp[i] += dp[以j为根节点左子树节点数量] * dp[以j为根节点右子树节点数量]，j相当于是根节点的元素，从1遍历到i为止。
 *    所以最终递推公式：dp[i] += dp[j - 1] * dp[i - j]。
 * 3. dp数组初始化
 *    从定义上来讲，空节点也是一棵二叉搜索树，从递归公式上来讲，
 *    dp[以j为根节点左子树节点数量] * dp[以j为根节点右子树节点数量] 中以j为根节点左子树节点数量为0，
 *    也需要dp[以j为根节点左子树节点数量] = 1，否则乘法的结果就都变成0了。
 *    所以可以初始化 dp[0] = 1。
 * 4. 确定遍历顺序
 *    从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠i之前节点数的状态。
 *    那么遍历i里面每一个数作为头节点的状态，用j来遍历。
 *    代码如下：
 *    for (int i = 1; i <= n; i++) {
 *        for (int j = 1; j <= i; j++) {
 *            dp[i] += dp[j - 1] * dp[i - j];
 *        }
 *    }
 * 5. 举例推导dp数组
 *    n 为5的时候，dp数组的状态如下：
 *    下标i:    0    1    2    3    4    5
 *    dp[o]:   1    1    2    5    14   42
 *
 * 另外一种思路：
 * 假设n个节点存在二叉排序树的个数是G(n)，1为根节点，2为根节点，...，n为根节点，当1为根节点时，其左子树节点个数为0，
 * 右子树节点个数为n-1，同理当2为根节点时，其左子树节点个数为1，右子树节点为n-2，
 * 所以可得G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)。
 *
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(n)
 *
 */
int Solution::uniqueBinarySearchTree(int n)
{
    vector<int> dp(n + 1);

    dp[0] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }

    return dp[n];
};

int main(int argc, char const *argv[])
{
    Solution s;

    cout << "n = 3, 二叉搜索树的个数: " << s.uniqueBinarySearchTree(3) << endl;
    cout << "n = 4, 二叉搜索树的个数: " << s.uniqueBinarySearchTree(4) << endl;
    cout << "n = 5, 二叉搜索树的个数: " << s.uniqueBinarySearchTree(5) << endl;
    return 0;
}