96. 不同的二叉搜索树

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution { public: int numTrees(int n) { std::vector<int> visited(n+1, -1); return dfs(n, visited); } private: int dfs(int n, std::vector<int>& visited) { if (n == 0 || n == 1) { return 1; } if (visited[n] != -1) { return visited[n]; } int result = 0; for (int i = 1; i <= n; ++i) { int tmp = dfs(i-1, visited) * dfs(n-i, visited); result += tmp; } visited[n] = result; return result; } };

class Solution { public: int numTrees(int n) { if (n <= 0) { return 0; } vector<vector<int>> memo(n+1, vector<int>(n+1, -1)); return dfs(1, n, memo); } int dfs(int start, int end, vector<vector<int>>& memo) { if (start >= end) { return 1; } if (memo[start][end] != -1) { return memo[start][end]; } int count = 0; for (int i = start; i <= end; ++i) { count += dfs(start, i-1, memo) * dfs(i+1, end, memo); } memo[start][end] = count; return count; } };