Создание треугольника Паскаля в словаре

Вы можете использовать zip, чтобы объединить список, возвращаемый из рекурсивного вызова, с тем же списком, но с одним индексом, дополненным 0:

def pascal(n):
    if n == 1:
        return {1: [1]}
    p = pascal(n - 1)
    p[n] = list(map(sum, zip([0] + p[n - 1], p[n - 1] + [0])))
    return p

так что:

for n in range(1, 6):
    print(pascal(n))

выходы:

{1: [1]}
{1: [1], 2: [1, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1], 4: [1, 3, 3, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1], 4: [1, 3, 3, 1], 5: [1, 4, 6, 4, 1]}

Если вы открыты для итеративного решения, я придумал следующее.

from itertools import chain 

def pascal(n):
    pad = (0,)
    result = {1: [1]}
    for i in range(2, n + 1):
        previous = list(chain(pad, result[i - 1], pad))
        result[i] = [sum(pair) for pair in zip(previous, previous[1:])]
    return result

Демо:

>>> for n in range(1, 6):
...:    print(pascal(n))
...:    
...:    
{1: [1]}
{1: [1], 2: [1, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1], 4: [1, 3, 3, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1], 4: [1, 3, 3, 1], 5: [1, 4, 6, 4, 1]}

С немного большим количеством строк, но с большей эффективностью памяти:

from itertools import chain, tee

def pascal(n):
    pad = (0,)
    result = {1: [1]}
    for i in range(2, n + 1):
        previous = chain(pad, result[i - 1], pad)
        c1, c2 = tee(previous)
        next(c2)
        result[i] = [sum(pair) for pair in zip(c1, c2)]
    return result

Наконец, наличие dict с последовательными целочисленными ключами не очень полезно, вы можете просто использовать список, в который вы индексируете, начиная с 0. Окончательное решение:

def pascal(n):
    pad = (0,)
    result = [[1]]
    for i in range(1, n):
        previous = chain(pad, result[i - 1], pad)
        c1, c2 = tee(previous)
        next(c2)
        result.append([sum(pair) for pair in zip(c1, c2)])
    return result

Демо:

>>> for n in range(1, 6):
...:    print(pascal(n))
...:    
[[1]]
[[1], [1, 1]]
[[1], [1, 1], [1, 2, 1]]
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

edit: повышена эффективность за счет отказа от создания двух кортежей на итерацию, достаточно одного экземпляра pad.

Я был бы осторожен с такой рекурсией - это очень неэффективно. Вы вызываете функцию дважды в цикле в теле функции. Важно подумать о том, сколько раз функция будет вызываться для оценки определенных значений n.

Очевидно, что при n = 1 функция вызывается один раз.

Когда n = 2, функция вызывается один раз, а затем функция вызывает себя дважды, всего 3 вызова.

Для n = 3 функция вызывается один раз, затем функция вызывает себя дважды, а затем эти два вызова вызывают функцию четыре раза ... Итак, это 11 вызовов.

Итак, количество звонков numCalls = 1 + 2 + 2*4 + 2*4*6 + ... + 2*4*6*...*2n)

Эта последовательность растет очень быстро ... Когда n равно 20, это 1308293051285742128434781 Звонки

Рекурсия - это не всегда зло, вам просто нужно быть осторожным, это решение вызывает себя n раз:

    def genPascalDict(nMax):
        if nMax < 2:
            return {1: [1]}
        else:
            pascalDict = genPascalDict(nMax - 1)
            lastRow = pascalDict[nMax - 1]
            pascalDict[nMax] = [1] + [lastRow[n + 1] + lastRow[nMax - n - 2] for n in range(nMax - 2)] + [1]
            return pascalDict

Вы можете сделать это быстро, создавая свой диктант в качестве побочного эффекта:

_cache = {}

def pascal(n):
    try:
        result = _cache[n]
    except KeyError:
        if n == 0:
            result = []
        elif n == 1:
            result = [1]
        else:
            previous = pascal(n - 1)
            result = [1] + [previous[i] + previous[i + 1] for i in range(n - 2)] + [1]
        _cache[n] = result
    return result

pascal(500)

print(_cache)

Вам не нужно вычислять pascal(n) больше одного раза: это не похоже на изменение. Так что запомните, каким был ваш окончательный ответ, сохранив его в кеширующем словаре, причем указанный словарь был тем, что вы действительно хотели в первую очередь.

На создание словаря на моем ноутбуке уходит около 0,08 с.

Вы можете использовать закрытие с рекурсией:

def pascal(n:int) -> dict:
  def _pascal(_s, _e, _last, _base={1:[1], 2:[1, 1]}):
    return _last if not _e-_s else _pascal(_s+1, _e, {**_last, **{_s:_base.get(_s, [1, *[_last[_s-1][i]+_last[_s-1][i+1] for i in range(len(_last)-1)], 1])}})
  return _pascal(1, n+1, {})

print(pascal(3))

Вывод:

{1: [1], 2: [1, 1], 3: [1, 2, 1]}