(DP)白駿2193号が親水

s = [0, 1, 1]
for i in range(3, 91):
  s.append(s[i - 2] + s[i - 1])
n = int(input())
print(s[n])

1から順に状況の数を書き出し、結果はs[i]がs[i-2]+s[i-1]であることを示した.
どうしてこんな結果になったのでしょうか.
この選手の一番前の数字は1でなければならないし、1は連続できないからだ.
一番前の数字は1が固定されていて、後ろに「0」と「01」が付いている場合にのみ適用されます.
例えば
3日間の場合は100101です.
4日間で1000、1010、1001
5日間で10000、10100、10010、10001、10101
結果iが持つことができる個数は,i−1の末尾に0,i−2の末尾に01を加える.だからs[i]=s[i-2]+s[i-1]の場合が成立する.