118. Pascal's Triangle

LeetCode задача 118

Задача

Дано целое число numRows. Верните первые numRows строк Треугольника Паскаля.

В Треугольнике Паскаля каждое число является суммой двух чисел, находящихся непосредственно над ним.

Подсказки

Для построения каждой следующей строки можно использовать последнюю строку в текущей итерации. Например, если есть строка [1, 2, 1], то следующая строка начнется и закончится с 1, а числа внутри будут получены путем сложения пар чисел: 1+2 и 2+1.

Подход

Для того чтобы построить Треугольник Паскаля, начнем с первой строки, состоящей только из числа 1. Для каждой следующей строки мы добавляем новое число, равное сумме двух чисел из предыдущей строки, которые стоят непосредственно над ним. Индексы этих двух чисел - это индекс текущего(искомого) числа в новом массиве и предыдущий индекс от него.

Это повторяем до тех пор, пока не достигнем нужного количества строк.

Алгоритм / Абстрактный алгоритм

1. Инициализируем список с первой строкой: [[1]].
2. Для каждой новой строки:
   • Начинаем строку с числа 1.
   • Для каждого числа в предыдущей строке (кроме последнего) добавляем к новой строке сумму этого числа и следующего за ним.
   • Заканчиваем строку числом 1.

Решение

class Solution:
    def generate(self, numRows: int):
        triangle = [[1]]                        #1

        for i in range(1, numRows):             #2
            prev_row = triangle[-1]             # Последняя строка в текущем треугольнике
            new_row = [1]                       # Новая строка начнется с 1

            for j in range(len(prev_row) - 1):  # Добавляем к новой строке сумму пар чисел из предыдущей строки
                new_row.append(prev_row[j] + prev_row[j + 1])
            
            new_row.append(1)                   # Заканчиваем строку числом 1
            triangle.append(new_row)            # Добавляем новую строку к треугольнику

        return triangle