dp-パスカルの三角形について
概要
- \(n\)段目、\(k\)番目の数は\({n-1} C{k-1}\)
- 公式がわからなくてもdpで簡単に求めることができる
具体例
指定の高さのパスカルの三角形を作る
def solve(lst=[], num=5, ret=[]):
if lst == []:
lst = [0, 1, 0]
else:
lst = [0] + lst + [0]
ret.append(lst[1:-1])
if len(ret) == num:
return
nxt = [0] * (len(lst)-1)
for i in range(0, len(lst)-1):
nxt[i] = lst[i] + lst[i+1]
solve(nxt, num, ret)
ret = []
solve([], 5, ret)
assert ret == [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]