質問編集履歴
3
タイトルの変更
test
CHANGED
|
@@ -1 +1 @@
|
|
|
1
|
-
階段の登り方は何通りあるか
|
|
1
|
+
階段の登り方は何通りあるか問題 d[i] = dp[i] + dp[i-a]の式の意味
|
test
CHANGED
|
@@ -73,4 +73,4 @@
|
|
|
73
73
|
|
|
74
74
|
両辺に```dp[i]```という項があることが非常に違和感があるのですが、この式はどのように解釈したらいいでしょうか。
|
|
75
75
|
```dp[i]```はi段目に行く経路だと認識しています。
|
|
76
|
-
```i```段目に行く経路に```i-a```段目に行く経路を足してi段目に行く経路になる理由がわかりません。
|
|
76
|
+
```i```段目に行く経路に```i-a```段目に行く経路を足してi段目に行く経路になる理由がわかりません。ご教授いただけたら嬉しいです。
|
2
質問内容変更
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -40,8 +40,37 @@
|
|
|
40
40
|
```ここに言語を入力
|
|
41
41
|
17
|
|
42
42
|
```
|
|
43
|
+
【調べて書いたコード】
|
|
44
|
+
```Ruby
|
|
45
|
+
def solve(gets)
|
|
46
|
+
n, a, b, c = gets.split.map(&:to_i)
|
|
47
|
+
# dpテーブル初期化
|
|
48
|
+
# 0段目には上らなくても到達できる
|
|
49
|
+
dp = [1] + [0] * n
|
|
50
|
+
# dpテーブル更新
|
|
51
|
+
1.upto(n) do |i|
|
|
52
|
+
# i-a 段目から a 段上って i 段へ到達
|
|
53
|
+
dp[i] += dp[i - a] if i >= a
|
|
54
|
+
# i-b 段目から b 段上って i 段へ到達
|
|
55
|
+
dp[i] += dp[i - b] if i >= b
|
|
56
|
+
# i-c 段目から c 段上って i 段へ到達
|
|
57
|
+
dp[i] += dp[i - c] if i >= c
|
|
58
|
+
end
|
|
59
|
+
# n 段目に行く経路数を返す
|
|
60
|
+
dp[n]
|
|
61
|
+
end
|
|
62
|
+
puts solve(gets)
|
|
63
|
+
```
|
|
43
64
|
|
|
44
65
|
【質問したいこと】
|
|
66
|
+
```
|
|
67
|
+
dp[i] += dp[i - a] if i >= a
|
|
68
|
+
```
|
|
45
|
-
こ
|
|
69
|
+
この行の式は次のようになるかと思います。
|
|
70
|
+
```
|
|
46
|
-
|
|
71
|
+
dp[i] = dp[i] + dp[i - a] if i >= a
|
|
72
|
+
```
|
|
73
|
+
|
|
47
|
-
|
|
74
|
+
両辺に```dp[i]```という項があることが非常に違和感があるのですが、この式はどのように解釈したらいいでしょうか。
|
|
75
|
+
```dp[i]```はi段目に行く経路だと認識しています。
|
|
76
|
+
```i```段目に行く経路に```i-a```段目に行く経路を足してi段目に行く経路になる理由がわかりません。
|
1
記述の訂正
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -43,5 +43,5 @@
|
|
|
43
43
|
|
|
44
44
|
【質問したいこと】
|
|
45
45
|
こちらの問題の解答として、どのようなコードがが考えられるでしょうか。
|
|
46
|
-
a
|
|
46
|
+
nをaで割った商aで場合分けし、その中で、(n-a×商a)をbで割った商bで場合分けし、またその中で(n-a×商a-b×商b)をcで割るといった力技で解くことしか思い浮かばない状況です。
|
|
47
47
|
おそらく、もっとスマートなコードの書き方があると思うので、よろしければ、ご教授いただけたら嬉しいです。
|