なんとな~くしあわせ?の日記

JavaとかAWSの設定とかをメモする技術ブログ

動的計画法で組み合わせの総数 nCr を求めてみる

もっと早い組み合わせの総数 (combination)の求め方

動的計画法 - DP(Dynamic Programming)

最近AtCoderの問題をちょろちょろ見ているのですが、その中でいわゆるDP(Dynamic Programming)が勝負の鍵を握っているということがわかりました。組み合わせの求め方についてはいろいろやってきましたが、以下の方法では巨大な組み合わせを算出すると時間がかかってしまいます。

nantonaku-shiawase.hatenablog.com
nantonaku-shiawase.hatenablog.com

Combinationのための動的計画法

英語圏のサイトだとDP自体ちゃんと体系化されているっぽいので、以下のサイトからアルゴリズムを学び、やり方を汎化してみます。

www.csegeek.com

Rubyによるサンプルプログラム
  • 要は2次元配列に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 であれば、1を設定(初期値っぽい)
  • j > i であれば、0を設定(計算に関係ないから)

それ以外は

  • 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については、固定値で先にすべての場合を求めておく方がよさそう