階段の登り方は何通りあるか問題 d[i] = dp[i] + dp[i-a]の式の意味

Question

【問題】
整数 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

【調べて書いたコード】

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段目に行く経路になる理由がわかりません。ご教授いただけたら嬉しいです。

Answer 1

aを1~7で場合分けし、その中で、bを場合分けし、またその中でcを場合分けする

残念ながら、そもそも問題文を正確に読めていません。
n, a, b, cはテストケースごとに固定されています。
たとえば入力例1は、aは2で固定です。

---

とりあえず単純に考えると
「階段を上るのに、1歩で a 段または b 段または c 段を上ることができるとき、n 段の階段を上る方法」の数を
長ったらしいのでstep(n,a,b,c)と呼ぶことにすると

• n = 0のとき 1通り
• n < 0 のとき 0通り
• それ以外のとき、 step(n-a,a,b,c) + step(n-b,a,b,c) + step(n-c,a,b,c)通り

です。

---

問題文でググると動的計画法の典型問題らしいので、動的計画法で解くのでしょう。

k=0, 1, 2, 3, 4, ..., nとして、
「階段を上るのに、1歩で a 段または b 段または c 段を上ることができるとき、k 段の階段を上る方法」の数をdp[k]とすると
dp[k] = dp[k-a] + dp[k-b] + dp[k-c] (インデックスが負になる場合を適宜考慮する)
dp[0] = 1
という関係になりますので
k=0から計算していけばよいです。

---

両辺にdp[i]という項があることが非常に違和感があるのですが、この式はどのように解釈したらいいでしょうか。

これなら分かりますか?

    sum = 0
    sum += dp[i - a] if i >= a
    # i-b 段目から b 段上って i 段へ到達
    sum += dp[i - b] if i >= b
    # i-c 段目から c 段上って i 段へ到達
    sum += dp[i - c] if i >= c

    dp[i] = sum

やっていることはこれと全く一緒です。

Comments

[Doffy09]

コメントありがとうございます。
たしかにそうですね。nをaやb,cで割った商で場合わけになりますね。
ただ、それでも力技でやる方法しか思い浮かばないです。

[ozwk]

追記しました

[ozwk]

> nをaやb,cで割った商で場合わけになりますね。

ちなみに商でどう場合分けるのでしょうか?

[Doffy09]

nをaで割った商から-1ずつしていって場合分けする感じに思っています。

[Doffy09]

ご回答ありがとうございます。
そのような感じだろうとは思ったのですが、dp[i]に意味が生じるとよくわからなくなっている状態です。
dp[i] = dp[i] + dp[i-a]
の式を日本語にするとイメージができなくなっています。

[ozwk]

* dp[i]を計算する直前の時点ではdp[i]の値は0である。
* dp[i]の計算にdp[i]は必要がない。

というわけで、回答で言う変数sumの代わりにdp[i]を使っているだけです。
プログラミング的な操作と数学的な意味を混ぜないように気をつけてください。

別な言い方をすれば
dp[i]にdp[i-a]とdp[i-b]とdp[i-c]をどんどん足しているだけです。

[Doffy09]

1.upto(n) do |i|
# i-a 段目から a 段上って i 段へ到達
puts dp[i]
dp[i] += dp[i - a] if i >= a
puts dp[i]
# 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
上のように、前後でdp[i]の内容を確認してみたところ、はじめのdp[i]は常に0になっていました。
なんとなくわかったようなきがします。