Ruby と Perl と Java で解く AtCoder ABC 129 C (後編) 動的計画法 - Qiita

階段数の組合せがフィボナッチ数に等しかったので、前編の解法が使えましたが、もっと汎用的に解けないものでしょうか。 そこで、オフィシャルの editorial にあります動的計画法の登場になります。 n, m = gets.split.map(&:to_i) MOD = 1_000_000_007 dp = Array.new(n + 2, 0) a = [] dp[0] = 1 m.times do |i| a[i] = gets.to_i dp[a[i]] = -1 end n.times do |i| next if dp[i] == -1 if dp[i + 1] != -1 dp[i + 1] += dp[i] dp[i + 1] %= MOD end if dp[i + 2] != -1 dp[i + 2] += dp[i] dp[i + 2] %= MOD end end pu