Official

C - 階段を登る方法 / Ways to Climb Stairs Editorial by sounansya


\(d[i]\) を「\(0\) 段目から \(i\) 段目ちょうどまで登ってくるまでの経路の個数」とした動的計画法を考えます。

\(i\) 段目へは \(i-1,i-2,i-3\) 段目から到達することができるので、遷移式は \(d[i]=d[i-1]+d[i-2]+d[i-3]\) となります。ただし、\(S_i\) が # である場合は \(d[i]=0\) となります。

以上の遷移を適切に \(10^9+7\) で割ったあまりを取りながら実装することでこの問題に正答することができます。

実装例(Python3)

n = int(input())
s = input()
d = [0] * (n + 1)
d[0] = 1
MOD = 10**9 + 7
for i in range(1, n + 1):
    for k in range(1, 4):
        j = i - k
        if j < 0:
            continue
        d[i] += d[j]
    d[i] %= MOD
    if s[i - 1] == "#":
        d[i] = 0
print(d[n])