DAY 27
1
Software Development

## [Day 27] 從LeetCode學演算法 - 0096. Unique Binary Search Trees (Medium)

``````Question:
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
``````
``````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
``````

(2跟3等價於1跟2兩個節點會有的組合)

f(0) * f(2) + f(1) * f(1) + f(2) * f(0)

f(0) * f(n-1) + f(1) * f(n-2) + … + f(n-1) * f(0)

Java:

``````class Solution {
public int numTrees(int n) {
int[] dp = new int[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];
}
}
``````

Python:

``````class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1

for i in range(1, n + 1):
for j in range(0, i):
dp[i] += dp[j] * dp[i - j - 1]

return dp[n]
``````

「時間/空間複雜度？」
(O(n²), O(n)

「可以改成遞迴的方式嗎？」
(可以，我們只要將dp改成字典或HashMap，開一個函式search，

0189. Rotate Array (Easy)