回答編集履歴
4
追記
test
CHANGED
|
@@ -27,3 +27,22 @@
|
|
|
27
27
|
という関係になりますので
|
|
28
28
|
`k=0`から計算していけばよいです。
|
|
29
29
|
|
|
30
|
+
|
|
31
|
+
---
|
|
32
|
+
|
|
33
|
+
> 両辺にdp[i]という項があることが非常に違和感があるのですが、この式はどのように解釈したらいいでしょうか。
|
|
34
|
+
|
|
35
|
+
これなら分かりますか?
|
|
36
|
+
|
|
37
|
+
```ruby
|
|
38
|
+
sum = 0
|
|
39
|
+
sum += dp[i - a] if i >= a
|
|
40
|
+
# i-b 段目から b 段上って i 段へ到達
|
|
41
|
+
sum += dp[i - b] if i >= b
|
|
42
|
+
# i-c 段目から c 段上って i 段へ到達
|
|
43
|
+
sum += dp[i - c] if i >= c
|
|
44
|
+
|
|
45
|
+
dp[i] = sum
|
|
46
|
+
```
|
|
47
|
+
|
|
48
|
+
やっていることはこれと全く一緒です。
|
3
追記
test
CHANGED
|
@@ -20,3 +20,10 @@
|
|
|
20
20
|
|
|
21
21
|
問題文でググると動的計画法の典型問題らしいので、動的計画法で解くのでしょう。
|
|
22
22
|
|
|
23
|
+
`k=0, 1, 2, 3, 4, ..., n`として、
|
|
24
|
+
「階段を上るのに、1歩で a 段または b 段または c 段を上ることができるとき、k 段の階段を上る方法」の数を`dp[k]`とすると
|
|
25
|
+
`dp[k] = dp[k-a] + dp[k-b] + dp[k-c]` (インデックスが負になる場合を適宜考慮する)
|
|
26
|
+
`dp[0] = 1`
|
|
27
|
+
という関係になりますので
|
|
28
|
+
`k=0`から計算していけばよいです。
|
|
29
|
+
|
2
追記
test
CHANGED
|
@@ -16,3 +16,7 @@
|
|
|
16
16
|
|
|
17
17
|
です。
|
|
18
18
|
|
|
19
|
+
---
|
|
20
|
+
|
|
21
|
+
問題文でググると動的計画法の典型問題らしいので、動的計画法で解くのでしょう。
|
|
22
|
+
|
1
追記
test
CHANGED
|
@@ -4,4 +4,15 @@
|
|
|
4
4
|
`n, a, b, c`はテストケースごとに固定されています。
|
|
5
5
|
たとえば入力例1は、`a`は`2`で固定です。
|
|
6
6
|
|
|
7
|
+
---
|
|
7
8
|
|
|
9
|
+
とりあえず単純に考えると
|
|
10
|
+
「階段を上るのに、1歩で a 段または b 段または c 段を上ることができるとき、n 段の階段を上る方法」の数を
|
|
11
|
+
長ったらしいので`step(n,a,b,c)`と呼ぶことにすると
|
|
12
|
+
|
|
13
|
+
* `n = 0`のとき `1`通り
|
|
14
|
+
* `n < 0` のとき `0`通り
|
|
15
|
+
* それ以外のとき、 `step(n-a,a,b,c) + step(n-b,a,b,c) + step(n-c,a,b,c)`通り
|
|
16
|
+
|
|
17
|
+
です。
|
|
18
|
+
|