向聴数の計算3 - ヤマカサのプログラミング勉強日記

向聴数の計算

自分の以前の方法では4色の和了形のパターン140くらいを全探索していましたが，動的計画法により効率化させます．

上記の記事の(7)式から(18)式まで何をやっているのかを考えてみました．

$d(i, j) (0 \leq i \leq 4, 0 \leq j \leq 9)$ を $i$ 色目まで探索したとき，和了形の個数が $n_j$ であるものの距離とします． $n_j$ の取りえる値は， $\{0, 2, 3, 5, 6, 8, 9, 11, 12, 14\}$ です．次に，色 $j$ の距離テーブルを $p_j$ とします．初期値は $d(0, \cdot) = p_0$ です．

更新式は，

$(1\leq i \leq 3, 0 \leq j \leq 4, 0 \leq k \leq j)$ $d(i, 2(j + k)) \leftarrow \min (d(i, 2 (i + k)), p_i(2j) + d(i - 1, 2k))$ $d(i, 2(j + k) + 1) \leftarrow \min (d(i, 2 (i + k) + 1), p_i(2j) + d(i - 1, 2k + 1), p_i(2j + 1) + d(i - 1, 2k))$

となります．求める向聴数は $d(3, 9)$ となります．

つまり， $d(i, \cdot)$ は $i$ 色を考慮した距離テーブルとなります．