struct Solution {}
impl Solution {
    pub fn num_trees(n: i32) -> i32 {
        if n <= 1 {
            return n;
        }
        let mut v = vec![0; (n + 1) as usize];
        v[0] = 1;
        v[1] = 1;
        return Solution::num_trees_internal(n as usize, &mut v);
    }
    pub fn num_trees_internal(n: usize, v: &mut Vec<i32>) -> i32 {
        if v[n] > 0 {
            return v[n];
        }
        let mut sum = 0;
        for i in 0..n {
            v[i] = Solution::num_trees_internal(i, v);
            v[n - i - 1] = Solution::num_trees_internal(n - i - 1, v);
            sum += v[i] * v[n - i - 1];
        }
        sum
    }
}
#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test_num_trees() {
        assert_eq!(1, Solution::num_trees(1));
        assert_eq!(2, Solution::num_trees(2));
        assert_eq!(5, Solution::num_trees(3));
    }
}