[アルゴリズム]
練習のための問題は 競技プログラミングの履歴
パスカルの三角形
- パスカルの三角形による二項係数(nCk)の計算 を参照せよ
- ref: Wikipedia - パスカルの三角形
以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、
上から n 行目・左から k 個目の数は、nCk に対応しています。(0-indexed)
そして、そのnCk部分は動的計画法で計算できる \( {}_{i}C_{j} = {}_{i−1}C_{j−1} + {}_{i−1}C_{j} \) を利用して計算（動的計画法）
588px-Pascal_triangle.svg.png