Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
Example:
Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
Solution: DP
dp[i] = sum(dp[j] * dp[i – j – 1]) (0 <= j < i )
root: 1 node
left child: j nodes
right child i – j – 1 nodes
try all possible partitions
ans = dp[n]
Time complexity: O(n^2)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int numTrees(int n) { vector<int> dp(n + 1); dp[0] = 1; for (int i = 1; i <= n; i++) for(int j = 0; j < i; j++) dp[i] += dp[j] * dp[i - j - 1]; return dp[n]; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment