プログラミングコンテストチャレンジブック演習「分割数」

今回のお題はこちら

漸化式の立て方がいまいちわからない。。実行結果がおかしいけど、先に進みたいので今時点のプログラムを載せます。

require 'pp'

N = 4 #input
M = 3 #input
Lm = 10000 #input

$dp = Array.new( M + 1 ).map!{ Array.new( N + 1, 0 ) }
$dp[0][0] = 1
for i in 1..M
  for j in 0..N
    if j - i >= 0
      if $dp[i - 1][j].nil? || $dp[i][j - i].nil?
        return true
      end
      $dp[i][j] = ($dp[i - 1][j] + $dp[i][j - i]) % M
    else
      $dp[i][j] = $dp[i - 1][j]
    end
  end
end

pp $dp
pp $dp[M][N]