96. Unique Binary Search Trees Medium

1/**
2 * [96] Unique Binary Search Trees
3 *
4 * Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
5 *  
6 * Example 1:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg" style="width: 600px; height: 148px;" />
8 * Input: n = 3
9 * Output: 5
10 * 
11 * Example 2:
12 * 
13 * Input: n = 1
14 * Output: 1
15 * 
16 *  
17 * Constraints:
18 * 
19 * 1 <= n <= 19
20 * 
21 */
22pub struct Solution {}
23
24// problem: https://leetcode.com/problems/unique-binary-search-trees/
25// discuss: https://leetcode.com/problems/unique-binary-search-trees/discuss/?currentPage=1&orderBy=most_votes&query=
26
27// submission codes start here
28
29impl Solution {
30    pub fn num_trees(n: i32) -> i32 {
31        let mut d: Vec<i64> = vec![0; n as usize + 1];
32        d[0] = 1; d[1] = 1;
33        for i in 2..n as usize + 1 {
34            for j in 1..i + 1 {
35                d[i] += d[j - 1] * d[i - j];
36            }
37        }
38        d[n as usize] as i32
39    }
40}
41
42// submission codes end
43
44#[cfg(test)]
45mod tests {
46    use super::*;
47
48    #[test]
49    fn test_96() {
50        assert_eq!(Solution::num_trees(1), 1);
51        assert_eq!(Solution::num_trees(3), 5);
52    }
53}
54