Вычисление биномиальных коэффициентов - EcsFlash/DataTypes GitHub Wiki

func BinomialCoefs(n int) []uint64 {
	var triangle [][]uint64 //инициализируем двумерный список - он же наш треугольник 
	triangle = append(triangle, []uint64{1})  // добавляем на вершину треугольника 1
	for i := 1; i <= n; i++ {
		temp := make([]uint64, i+1) // создаем новую строку, которая затем попадет в треугольник
		temp[0], temp[i] = 1, 1 // первый и последний элемент любой строки - 1, ставим их
		for j := 1; j < i/2+1; j++ { // идем до середины строки(середину включаем)
			temp[j] = triangle[i-1][j-1] + triangle[i-1][j]  // jый элемент строки равен сумме j-1 и j элементов предыдущей строки(j >= 1 и j < len текущей строки)
			temp[i-j] = temp[j] //коэфы в строке располагаются симметрично
		}
		triangle = append(triangle, temp) // добавляем получившуюся строку в треугольник
	}
	return triangle[n] // возвращаем треугольник
}

┌────────────┬────────────────┬──────────────────┬────────────────┐
│            │  Лучший случай │  Средний случай  │  Худший случай │
├────────────┼────────────────┼──────────────────┼────────────────┤
│ **Время**  │     O(n²)      │      O(n²)       │     O(n²)      │
├────────────┼────────────────┼──────────────────┼────────────────┤
│ **Память** │     O(n²)      │      O(n²)       │     O(n²)      │
└────────────┴────────────────┴──────────────────┴────────────────┘

А можно сократить потребление памяти, храня только текущую и предыдущую строку треугольника:

func BinomialCoefsOpt(n int) []uint64 {
	if n == 0 {
		return []uint64{1}
	}
	prev := []uint64{1, 1}
	for i := 2; i <= n; i++ {
		curr := make([]uint64, i+1)
		curr[0], curr[i] = 1, 1
		for j := 1; j < i/2+1; j++ {
			curr[j] = prev[j-1] + prev[j]
			curr[i-j] = curr[j]
		}
		prev = curr
	}
	return prev
}

┌────────────┬────────────────┬──────────────────┬────────────────┐
│            │  Лучший случай │  Средний случай  │  Худший случай │
├────────────┼────────────────┼──────────────────┼────────────────┤
│ **Время**  │     O(n²)      │      O(n²)       │     O(n²)      │
├────────────┼────────────────┼──────────────────┼────────────────┤
│ **Память** │     O(n)       │      O(n)        │     O(n)       │
└────────────┴────────────────┴──────────────────┴────────────────┘