プログラミングコンテストチャレンジブック演習「重複組合せ」

今回のお題はこちら。

漸化式中のΣを取り除く式変形が難しいですな。

$m = 3 #input
A = [1, 2, 3] #input
M = 10000 #input

$dp = Array.new( A.length + 1 ).map!{ Array.new( $m + 1, 0 ) }
for i in 0..A.length
  $dp[i][0] = 1
end

for i in 0..(A.length - 1)
  for j in 1..$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]] + M) % M
    else
      $dp[i + 1][j] = ($dp[i + 1][j - 1] + $dp[i][j]) % M
    end
  end
end

puts $dp[-1][-1]