動的計画法で組み合わせの総数 nCr を求めてみる
もっと早い組み合わせの総数 (combination)の求め方
動的計画法 - DP(Dynamic Programming)
最近AtCoderの問題をちょろちょろ見ているのですが、その中でいわゆるDP(Dynamic Programming)が勝負の鍵を握っているということがわかりました。組み合わせの求め方についてはいろいろやってきましたが、以下の方法では巨大な組み合わせを算出すると時間がかかってしまいます。
nantonaku-shiawase.hatenablog.com
nantonaku-shiawase.hatenablog.com
Combinationのための動的計画法
英語圏のサイトだとDP自体ちゃんと体系化されているっぽいので、以下のサイトからアルゴリズムを学び、やり方を汎化してみます。
Rubyによるサンプルプログラム
- 要は２次元配列にnCrの答えを予め用意しておき、後で使う時は添字アクセスするのだ
def choose(n, r) 1 if r == 0 or r == n # store C(n,r) in a matrix c = Array.new(n+1).map{Array.new(r+1,0)} i,j = 0 for i in 0..n # C(i,0) = 1 for i = 0...n c[i][0] = 1 end for j in 0..r # if n = 0, C(n,r) = 0 for all 'r' c[0][j] = 0 end for i in 1..n for j in 1..r if i == j # C(n,n) = 1 c[i][j] = 1 elsif j > i # case when r > n in C(n,r) c[i][j] = 0 else # apply the standard recursive formula c[i][j] = c[i-1][j-1] + c[i-1][j] end end end return c[n][r] end n = 5 r = 2 comb = choose(n,r) puts "C (#{n},#{r}) = #{comb}"
処理内容を表で表現してみる
- nCr , n = 3, r = 2 を求める
1. 行 n、列 r の格子を考える
| (0,0) | (0,1) | (0,2) |
|---|---|---|
| (1,0) | (1,1) | (1,2) |
| (2,0) | (2,1) | (2,2) |
| (3,0) | (3,1) | (3,2) |
2. C(i,0) = 1 for i = 0...n
| (0,0) = 1 | (0,1) | (0,2) |
|---|---|---|
| (1,0) = 1 | (1,1) | (1,2) |
| (2,0) = 1 | (2,1) | (2,2) |
| (3,0) = 1 | (3,1) | (3,2) |
3. if n = 0, C(n,r) = 0 for all r
| (0,0) = 0 | (0,1) = 0 | (0,2) = 0 |
|---|---|---|
| (1,0) = 1 | (1,1) | (1,2) |
| (2,0) = 1 | (2,1) | (2,2) |
| (3,0) = 1 | (3,1) | (3,2) |
4. j と i、それぞれ 1から最大値まで
- i == j であれば、１を設定（初期値っぽい）
- j > i であれば、０を設定（計算に関係ないから）
それ以外は
- c[i][j] = c[i-1][j-1] + c[i-1][j]
- 斜め左上のセルと上のセルを合計したものがそのセルの値
| (0,0) = 0 | (0,1) = 0 | (0,2) = 0 |
|---|---|---|
| (1,0) = 1 | (1,1) = 1 | (1,2) = 0 |
| (2,0) = 1 | (2,1) = 2 | (2,2) = 1 |
| (3,0) = 1 | (3,1) = 3 | (3,2) = 3 |
実際使う時は
- nCr の NとRについては、固定値で先にすべての場合を求めておく方がよさそう
