【問題】
整数 n, a, b, c が与えられます。
階段を上るのに、1歩で a 段または b 段または c 段を上ることができるとき、n 段の階段を上る方法は何通りあるでしょうか。(Rubyのコードで解答してください。)
入力される値
n a b c
期待する出力
n 段の階段を上る方法の数を1行に出力してください。
条件
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 30 ・ 1 ≦ a ≦ 7 ・ 1 ≦ b ≦ 7 ・ 1 ≦ c ≦ 7 ・ a ≠ b ・ b ≠ c ・ c ≠ a
入力例1
10 2 3 4
出力例1
17
【調べて書いたコード】
Ruby
def solve(gets) n, a, b, c = gets.split.map(&:to_i) # dpテーブル初期化 # 0段目には上らなくても到達できる dp = [1] + [0] * n # dpテーブル更新 1.upto(n) do |i| # i-a 段目から a 段上って i 段へ到達 dp[i] += dp[i - a] if i >= a # i-b 段目から b 段上って i 段へ到達 dp[i] += dp[i - b] if i >= b # i-c 段目から c 段上って i 段へ到達 dp[i] += dp[i - c] if i >= c end # n 段目に行く経路数を返す dp[n] end puts solve(gets)
【質問したいこと】
dp[i] += dp[i - a] if i >= a
この行の式は次のようになるかと思います。
dp[i] = dp[i] + dp[i - a] if i >= a
両辺にdp[i]
という項があることが非常に違和感があるのですが、この式はどのように解釈したらいいでしょうか。
dp[i]
はi段目に行く経路だと認識しています。
i
段目に行く経路にi-a
段目に行く経路を足してi段目に行く経路になる理由がわかりません。ご教授いただけたら嬉しいです。
まだ回答がついていません
会員登録して回答してみよう