[swift] LeetCode 96. Unique Binary Search Trees

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

func numTrees(_ n: Int) -> Int {
    list = Array(repeating: 1, count: n+1)
    if n >= 2 { list[2] = 2 }
    return g(n)
}

private var list: [Int]!
private func g(_ n: Int) -> Int {
    if  n > 2 && list[n] == 1 {
        list[n] = (1...n).reduce(0) { $0 + f($1, n) }
    }
    return list[n]
}

private func f(_ i: Int, _ n: Int) -> Int {
    return g(i-1) * g(n-i)
}

func numTrees(_ n: Int) -> Int {

list = Array(repeating: 1, count: n+1)

if n >= 2 { list[2] = 2 }

return g(n)

}

private var list: [Int]!

private func g(_ n: Int) -> Int {

if n > 2 && list[n] == 1 {

list[n] = (1...n).reduce(0) { $0 + f($1, n) }

}

return list[n]

}

private func f(_ i: Int, _ n: Int) -> Int {

return g(i-1) * g(n-i)

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版