//
//  1.12 Unique Binary Search Trees.swift
//  leetCode
//
//  Created by czw on 8/15/20.
//  Copyright © 2020 czw. All rights reserved.
//

import Foundation

/*
 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
 
 示例:
 
 输入: 3
 输出: 5
 解释:
 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
 
 1         3     3      2      1
  \       /     /      / \      \
   3     2     1      1   3      2
  /     /       \                 \
 2     1         2                 3
 
 分析：推导公式不好找
 标签：动态规划
 假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数，则
 G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)
 
 当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，则
 f(i)=G(i−1)∗G(n−i)
 
 综合两个公式可以得到 卡特兰数 公式
 G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+...+G(n−1)∗G(0)
 
 int[] dp = new int[n+1];
 dp[0] = 1;
 dp[1] = 1;
 
 for(int i = 2; i < n + 1; i++)
 for(int j = 1; j < i + 1; j++)
 dp[i] += dp[j-1] * dp[i-j];
 
 return dp[n];
 */
class UniqueBinarySearchTrees {
  func numTrees(_ n: Int) -> Int {
    if n < 2 { return 1 }
    
    var dp = [Int].init(repeating: 0, count: n + 1)
    
    dp[0] = 1
    dp[1] = 1
    for i in 2...n {
      for j in 1...(i+1) {
        dp[i] += dp[j-1] * dp[i-j]
      }
    }
    return dp[n]
  }
}

extension UniqueBinarySearchTrees: Algorithm {
  func doTest() {
    
  }
}
