二項係数 - パスカルの三角形

パスカルの三角形を用いて, \(1 \leq n \leq N, 0 \leq k \leq n\) についての \(\left(\begin{array}{c}n\\k\end{array}\right)\)\(O(N^2)\) で求める.

二次元配列 binom を返し, \(\left(\begin{array}{c}n\\k\end{array}\right)\)binom[n][k] に入ってる. 範囲外にはゼロが入ってる.

/// Binomial Coefficient - Pascal's Triangle
fn pascal_triagle(n: usize) -> Vec<Vec<u64>> {
    let mut binom = vec![vec![0; n + 1]; n + 1];
    for i in 1..n + 1 {
        for j in 0..i + 1 {
            binom[i][j] = {
                if i == 1 || j == 0 {
                    1
                } else if j + j > i {
                    binom[i][i - j]
                } else {
                    binom[i - 1][j] + binom[i - 1][j - 1]
                }
            };
        }
    }
    binom
}