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 .

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

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

Q: Почему треугольник Паскаля — это задача на динамическое программирование?

Каждая запись зависит от двух меньших подзадач — записей над ней, и эти подзадачи сильно перекрываются: обычная рекурсия пересчитывает их снова и снова. Построение строк по порядку позволяет сохранить каждую подзадачу один раз и повторно использовать её, что превращает экспоненциальную сложность в O(n²) .

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

+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].

+13 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 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(2, 1) лежит под почти каждым значением ниже.

Алгоритм

Напишите 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 с r + 1 единиц — так задаются оба края. Затем для каждой внутренней позиции c от 1 до r-1 присвойте ей значение above[c-1] + above[c]. В строках 0 и 1 нет внутренних позиций, поэтому они остаются [1] и [1, 1] без особого случая.

Треугольник содержит 1 + 2 + ... + n, то есть примерно n²/2 элементов, и каждый требует постоянного времени, поэтому вычисления занимают O(n²). Помимо результата, который в любом случае нужно вернуть, методу не требуется дополнительная память. При numRows = 30 это 465 элементов вместо двух миллиардов вызовов.

Алгоритм

Начни с пустого списка строк.
Для каждого 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 нет правого родителя, поэтому чтение above[col-1] или above[col] там выходит за границы массива. Заполняйте только позиции с 1 по row-1.
Запись диапазона, который не работает для коротких строк. В Swift выражение 1..<row вызывает сбой, если row равно 0, а в R выражение 2:(row-1) при row, равном 2, отсчитывает в обратном порядке до 1. Добавьте проверки или задавайте внутренние позиции как единицы, чтобы для строк 0 и 1 цикл не требовался.
Вычисление элементов с помощью факториалов. C(29, 14) помещается в int, но 29! переполняет даже 64-битное целое число, поэтому формула на основе факториалов выводит неверные числа в нижних строках.
Повторное использование одного массива для каждой строки. Если каждый раз добавлять один и тот же массив, а затем изменять его, в ответе все строки окажутся такими же, как последняя.

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

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

Построение каждой строки на основе предыдущей занимает время 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.

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

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

Почему треугольник Паскаля — это задача на динамическое программирование?

Каждая запись зависит от двух меньших подзадач — записей над ней, и эти подзадачи сильно перекрываются: обычная рекурсия пересчитывает их снова и снова. Построение строк по порядку позволяет сохранить каждую подзадачу один раз и повторно использовать её, что превращает экспоненциальную сложность в O(n²).

Python

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

Тестовые случаи

Случай 1

Случай 2

Ввод

numRows = 5

Ожидается

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