重複組合せ

repeated_combination.rb

## 重複組合せ
## http://rubyfiddle.com/riddles/aba0f

n = 3
m = 3
a = [1, 2, 3]
M = 10000

dp = Array.new(n+1,0).map{Array.new(m+1,0)}
(n+1).times{|i|
  dp[i][0] = 1
  }

n.times{|i|
  j = 1
  while j <= m
    if (j-1-a[i]) >= 0
      dp[i+1][j] = (dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a[i]])
    else
      dp[i+1][j] =(dp[i+1][j-1]+dp[i][j])
    end
    j += 1  
  end
  }

puts dp[n][m]