unique_trees_dp.go

// https://leetcode.com/problems/unique-binary-search-trees

func numTrees(n int) int {
    if n == 0 {
        return 1
    }
    
    memorized := make([][]int, n + 2)
    
    for i, _ := range memorized {
        memorized[i] = make([]int, n + 2)
    }
    
    return calcNumTreesInRange(1, n, memorized)
}

func calcNumTreesInRange(min, max int, memorized [][]int) int {
    total := 0
    
    for i := min; i <= max; i++ {
        if memorized[min][i - 1] == 0 {
            memorized[min][i - 1] = calcNumTreesInRange(min, i - 1, memorized)
        }
        
        if memorized[i + 1][max] == 0 {
            memorized[i + 1][max] = calcNumTreesInRange(i + 1, max, memorized)
        }
        
        left := memorized[min][i - 1]
        right := memorized[i + 1][max]
        total += left * right
    }
    
    if total == 0 {
        total = 1
    }
    
    return total
}