/*
 * @lc app=leetcode.cn id=96 lang=cpp
 *
 * [96] 不同的二叉搜索树
 */

// @lc code=start
class Solution {
public:
    vector<vector<int> > seen;

    int numTrees(int n) {
        for (int i = 0; i <= n+1; i++) {
            vector<int> tmp(n+1);
            seen.emplace_back(tmp);
        }
        return count(1, n);
    }

    int count(int lo, int hi) {
        if (lo > hi) return 1;
        if (seen[lo][hi] != 0) return seen[lo][hi];

        int res = 0;
        for (int i = lo; i <= hi; i++) {
            int left = count(lo, i - 1);
            int right = count(i + 1, hi);
            res += left * right;
        }
        seen[lo][hi] = res;

        return res;
    }
};
// @lc code=end