ABC312_D – Count Bracket Sequences

問題
提出
1. 2回目で解けた

問題

D - Count Bracket Sequences

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

提出

Submission #45114508 - UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312)

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

2回目で解けた

メモ化再帰で解けた。

まず、再帰で解くことを考える。
i番目までのcnt=左括弧の数-右括弧の数とすると、cnt>=0でなくてはならない。
cnt>=0を保ったままiを大きくしていく(つまり、右に文字を見ていく)。
最後の文字まで見た時、cnt==0なら括弧列になる。
この関数を$f(i,cnt)$とする。

これを再帰を使って実装すると、NをSの文字列長として、$O(2^N)$になり間に合わない。
そこで、メモをすることを考える。
i番目まで見た時のcntが決まれば、値は一意に決まるのでこれを記録する。
つまり、$dp[i][cnt]= f(i,cnt)$とする。
$i,cnt$は最大で$N$になるので$O(N^2)$となり間に合う。