LeetCode 96. Unique Binary Search Trees 파이썬, 해설, 풀이
접근
- 전체 node 가 head를 제외하고 n개일 때 head 에서 왼쪽에 k, 오른쪽에 n-k 만큼의 node를 갖는 경우의 수는 dp[k] * dp[n - k] 이다.
- 경우의 수를 곱해서 찾기 때문에 dp[0] 은 1로 둔다.
사고
예제 그림에서 보듯이 가능한 현재 경우의 수는 이전의 경우의 수 전체를 왼쪽 subtree, 오른쪽 subtree 로 갖는 경우로 생각해서 dp[i - 1] * 2 + ? 으로 시작했다. 이건 왼쪽에 dp[n - 1] 개, 오른쪽 0 그리고 오른쪽 dp[n - 1], 왼쪽 0 개를 가지는 하나의 케이스라고 생각했다. 그래서 모든 경우의 수를 수도코드로 생각하고 아래와 같이 구현했다.
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * 20
dp[0] = 1
dp[1] = 1
# left subtree having 0~n-1 while right having n-1~0
for i in range(2, 20):
sum = 0
for j in range(0, i // 2):
sum += dp[j] * dp[i - j - 1]
sum *= 2
if i % 2 == 1:
sum += dp[i // 2] * dp[i // 2]
dp[i] = sum
return dp[n]
