问题描述
https://leetcode.com/problems/unique-binary-search-trees/
代码
class Solution {
public int numTrees(int n) {
if(n < 1) return 0;
int[] nums = new int[n + 1];
nums[0] = 1;
nums[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 0; j < i; j++){
nums[i] += (nums[i - j - 1] * nums[j]);
}
}
return nums[n];
}
}
复杂度分析
- 时间复杂度：O(2^n)
- 空间复杂度：O(n)
