LeetCode #118 Треугольник Паскаля

Легкий

Проблема

Учитывая неотрицательное целое число numRows, сгенерируйте первые numRows треугольника Паскаля.

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

Пример:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Решение

Используйте подход динамического программирования. Мы не вычисляем значения рекурсивно, а используем информацию последнего уровня для вычисления информации текущего уровня.

Уравнение вычисления новой информации:

matrix[row][col] = matrix[row-1][col-1] + matrix[row-1][col]

Сложность

Строка 18 будет выполнена row — 2 раза, а значение row находится между 2 и n-1, где n равно numRows. Это означает, что строка 18 будет выполняться как 1+ 2 + … + (n-2) = O((n-2)*(n-1) / 2) = O(n²). Поэтому временная сложность составляет O(n²).

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