AtCoder Beginner Contest 189 D - Logical Expression【Python】

https://atcoder.jp/contests/abc189/tasks/abc189_d

AtCoder ProblemsでDifficulty: 769、Solve Probability: 32%でした。

動的計画法で解くことができましたが、思いつくのと実装に時間がかかってしまいました。
最近のABCでも桁DPなるもので解ける問題が出ていることもあるため、動的計画法全般について慣れていきたいです。

N = int(input())
S = []
for i in range(N):
    s = input()
    S.append(s)

# dp[i][j]: 文字列Siまで見たときの状態がj(False or True)のときの数
dp = [[0] * 2 for _ in range(N + 1)]
dp[0] = [1, 1]
for i in range(1, N+1):
    if S[i-1] == "AND":
        # F∧T, F∧F, T∧F（1つ前のFからの遷移が2つ、1つ前のTからの遷移が1つ)
        dp[i][0] += dp[i-1][0] * 2 + dp[i-1][1]
        # T∧T（1つ前のTからの遷移が1つ)
        dp[i][1] += dp[i-1][1]
    else:
        # F∨F（1つ前のFからの遷移が1つ)
        dp[i][0] += dp[i-1][0]
        # F∨T, T∨F, T∨T（1つ前のFからの遷移が1つ、1つ前のTからの遷移が2つ)
        dp[i][1] += dp[i-1][0] + dp[i-1][1] * 2

print(dp[N][1])