DP 응용, 파스칼 삼각형

파스칼 삼각형

n = 5
arr = [0] * (n + 1) # 크기를 정한다
arr[0] = [1]
arr[1] = [1, 1]
for i in range(2, n + 1):  # 2부터 만든다
    tmp = [1]
    for j in range(i - 1):
        # 앞의 리스트의 인접한 항을 더해서 만든다
        tmp += [arr[i - 1][j] + arr[i - 1][j + 1]]
    tmp += [1]
    arr[i] = tmp
print(arr[n])  # =>[1, 5, 10, 10, 5, 1]
print(arr)  #=> [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]

append 안쓰고

n = 5
arr = [0] * (n + 1)
arr[0] = [1]
arr[1] = [1, 1]
for i in range(2, n + 1):
    tmp = [0] * (i + 1)
    tmp[0] = 1
    tmp[i] = 1
    for j in range(i - 1):
        tmp[j + 1] = arr[i - 1][j] + arr[i - 1][j + 1]
    arr[i] = tmp
print(arr[n])
print(arr)