Задача: 119. Pascal's Triangle ll
Сложность: easy

Для данного целого числа rowIndex верните rowIndex-ю строку (с индексацией с нуля) треугольника Паскаля.

Пример:

Input: rowIndex = 3
Output: [1,3,3,1]

👨‍💻 Алгоритм:

1⃣Давайте представим, что у нас есть функция getNum(rowIndex, colIndex), которая дает нам число с индексом colIndex в строке с индексом rowIndex. Мы могли бы просто построить k-ю строку, повторно вызывая getNum(...) для столбцов от 0 до k.

2⃣Мы можем сформулировать нашу интуицию в следующую рекурсию:

getNum(rowIndex, colIndex) = getNum(rowIndex - 1, colIndex - 1) + getNum(rowIndex - 1, colIndex)

3⃣Рекурсия заканчивается в некоторых известных базовых случаях:

Первая строка - это просто одинокая 1, то есть getNum(0, ...) = 1

Первое и последнее число каждой строки равно 1, то есть getNum(k, 0) = getNum(k, k) = 1

😎 Решение:

class Solution {
    func getNum(_ row: Int, _ col: Int) -> Int {
        if row == 0 col==0 row == col {
            return 1
        }
        return getNum(row - 1, col - 1) + getNum(row - 1, col)
    }

    func getRow(_ rowIndex: Int) -> [Int] {
        var ans = [Int]()
        for i in 0...rowIndex {
            ans.append(getNum(rowIndex, i))
        }
        return ans
    }
}

Ставь 👍 и забирай 📚 Базу знаний