今回のお題はこちら。
漸化式中のΣを取り除く式変形が難しいですな。
$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]