Pascal's Triangle

Q: Какова временная сложность построения треугольника Паскаля?

O(n²) для n строк: в треугольнике примерно n²/2 элементов, и для каждого требуется одно сложение. Это оптимально, поскольку необходимо записать каждый элемент результата. Дополнительная память, не считая результата, составляет O(1) .

Q: Как треугольник Паскаля связан с биномиальными коэффициентами?

Элемент k строки r , если считать с 0, равен C(r, k) — числу способов выбрать k элементов из r . Правило суммы выражается тождеством C(r, k) = C(r-1, k-1) + C(r-1, k) , а сумма элементов строки r равна 2^r — числу подмножеств из r элементов.

Q: Можешь вычислить одну строку, не строя строки над ней?

Да. Начни с 1 и получай каждое следующее значение из предыдущего: C(r, k) = C(r, k-1) × (r-k+1) / k . Умножай перед делением, чтобы деление было точным, и используй 64-битное целое число для произведения. Тогда строка r занимает время O(r) .

ЛегкоДинамическое программирование

+10

В треугольнике Паскаля первая строка — [1]. Каждая следующая строка на один элемент длиннее, начинается и заканчивается числом 1, а каждый элемент между ними равен сумме двух элементов непосредственно над ним. Тебе дано целое число numRows. Верни первые numRows строк треугольника, начиная с верхней строки; каждая строка должна быть массивом целых чисел.

Функция

generate(numRows: integer) → integer-2d-array

numRowsinteger: сколько строк треугольника нужно построить
Возвращаетinteger-2d-array: первые numRows строк, сначала верхняя строка

Ограничения

1 ≤ numRows ≤ 30
Каждая запись в первых 30 строках помещается в 32-разрядное целое число со знаком. Наибольшее число — 77558760, оно находится посередине 30-й строки.

Примеры

Ввод: numRows = 5
Вывод: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Пояснение: Каждая внутренняя запись складывает два числа над ней. Четвёртая строка: 3 = 1 + 2 и 3 = 2 + 1. Пятая строка: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.

Ввод: numRows = 1
Вывод: [[1]]
Пояснение: С одной строкой треугольник состоит только из своей вершины: [1].

Дополнительный вопрос

Можешь оставить только один массив и обновлять его на месте, строка за строкой? В каком направлении должен выполняться внутренний цикл и почему?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Элемент — это сумма двух элементов в строке выше. Если каждый раз заново вычислять это правило для каждого элемента, одни и те же значения будут вычисляться повторно, а объём работы будет удваиваться с каждой строкой. Возвращаемые тобой строки — это сохранённые ответы на эти меньшие задачи, поэтому строй треугольник сверху вниз, формируя каждую строку из предыдущей.

Вычисляйте каждый элемент рекурсивно

Верно, но не успевает на самых больших тестах

Идея

Нумеруй строки и позиции с 0. Определение становится функцией: entry(row, col) равна 1 на краях, где col равно 0 или row, а в остальных случаях — entry(row-1, col-1) + entry(row-1, col). Это верно, потому что таково определение.

Рекурсия останавливается только на краях, где возвращается 1, поэтому для вычисления элемента со значением v требуется примерно 2v вызовов. Сумма элементов строки r равна 2^r, поэтому для 30 строк потребуется примерно 2^31 вызовов — больше двух миллиардов.

Алгоритм

Напиши entry(row, col): возвращай 1, если col равен 0 или col равен row.
В противном случае возвращай entry(row-1, col-1) + entry(row-1, col).
Для каждого row от 0 до numRows-1 собери entry(row, col) для каждого col от 0 до row.
Верни список строк.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Создайте каждую строку на основе строки выше

Идея

Рекурсия продолжает запрашивать элементы предыдущих строк, и вы всё равно строите эти строки. Поэтому вычисляйте строки сверху вниз, а при заполнении строки r читайте строку r-1, которая уже готова. На каждый элемент требуется одно сложение: таблица меньших результатов и есть сам вывод.

Если начинать каждую строку с r + 1 единиц, задаются оба края, поэтому для строк 0 и 1, в которых нет внутренних позиций, не нужен особый случай. В треугольнике 1 + 2 + ... + n, то есть примерно n²/2 элементов, поэтому трудоёмкость составляет O(n²), а дополнительная память не нужна: 465 элементов для 30 строк вместо двух миллиардов вызовов.

Алгоритм

Начни с пустого списка строк.
Для каждой row от 0 до numRows-1 создай row + 1 единиц.
Для каждого col от 1 до row-1 присвой ему сумму элементов на позициях col-1 и col предыдущей строки.
Добавь строку и продолжай. Верни список.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Ловушки и крайние случаи

Возврат numRows + 1 строк. Нумерация начинается с 0, поэтому последняя нужная строка — numRows-1.
Выполнение внутреннего цикла по рёбрам. У позиции 0 нет родителя слева, а у позиции row — справа, поэтому попытка прочитать их приводит к выходу за границы.
Диапазон, который ломается на коротких строках. В Swift диапазон 1..<row вызывает сбой, когда row равно 0, а диапазон R 2:(row-1) при row, равном 2, отсчитывает значения в обратном порядке до 1.
Вычисление элементов с помощью факториалов. C(29, 14) помещается в int, но 29! переполняет даже 64-битное целое число.
Добавление одного и того же массива для каждой строки с последующим его изменением. В ответе все строки станут последней строкой.

Частые вопросы3

Какова временная сложность построения треугольника Паскаля?

O(n²) для n строк: в треугольнике примерно n²/2 элементов, и для каждого требуется одно сложение. Это оптимально, поскольку необходимо записать каждый элемент результата. Дополнительная память, не считая результата, составляет O(1).

Как треугольник Паскаля связан с биномиальными коэффициентами?

Элемент k строки r, если считать с 0, равен C(r, k) — числу способов выбрать k элементов из r. Правило суммы выражается тождеством C(r, k) = C(r-1, k-1) + C(r-1, k), а сумма элементов строки r равна 2^r — числу подмножеств из r элементов.

Можешь вычислить одну строку, не строя строки над ней?

Да. Начни с 1 и получай каждое следующее значение из предыдущего: C(r, k) = C(r, k-1) × (r-k+1) / k. Умножай перед делением, чтобы деление было точным, и используй 64-битное целое число для произведения. Тогда строка r занимает время O(r).

def generate(numRows):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

numRows = 5

Ожидаемый вывод

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]