nCr を DP する
$ _n{\rm C}_rを DP で求める
$ _n{\rm C}_r=\frac{n!}{r!(n-r)!}なので
$ _{n+1}{\rm C}_{r+1}=\frac{(n+1)!}{(r+1)!(n-r)!}=\frac{(n+1)!}{(r+1)!}\cdot\frac1{(n-r)!}
このことを利用すると$ _n{\rm C}_rを漸化式になるように分解できる
$ _n{\rm C}_r=a_{n,r}\cdot\frac{1}{(n-r)!}
$ a_{n+1,r+1}=\frac{n}{r}\cdot a_{n,r}
計算量的には階乗を用いてナイーブに計算するのとあまり変わらない気がする
$ _{n+1}{\rm C}_{r+1}=_{n}{\rm C}_{r}+_{n}{\rm C}_{r+1}を利用した DP
しれっと乗算が無くなっている
2次元DPになる