Swift solution - DP


  • 0
    class Solution {
        func numTrees(_ n: Int) -> Int {
            if n <= 1 {
                return 1
            }
            var dp = [Int](repeatElement(0, count: n + 1))
            
            dp[0] = 1
            dp[1] = 1
            
            for i in 2...n {
                for j in 1...i {
                    dp[i] += dp[j - 1] * dp[i - j]
                }
            }
            
            return dp[n]
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.