Solutions of Regular bracket sequence 2

Select solution language

chithanhnguyen Created at 2 likes

## Thuật toán Gọi $\texttt{dp[l][r]}$ là số lượng ngoặc ít nhất để biến đoạn $S[l\ldots r]$ thành dãy ngoặc đúng. **Trường hợp cơ sở.** $\texttt{dp[l][l]} = 1 \ \forall l : 1 \leq l \leq n$. **Công thức truy hồi.** Để biến đoạn $S[l\ldots r]$ thành dãy ngoặc đúng, ta có thể lần lượt biến hai đoạn $S[l\ldots k]$ và $S[k + 1\ldots r]$ thành dãy ngoặc đúng. $\rightarrow$ Số ngoặc tối thiểu cần thêm vào là $\texttt{dp[l][k]} + \texttt{dp[k + 1][r]}$. Để cực tiểu hóa $\texttt{dp[l][r]}$, ta cần chọn $k$ sao cho biểu thức trên được cực tiểu hóa, vì thế: $$\texttt{dp[l][r]} = \min_{l \leq k < r}\left(\texttt{dp[l][k]} + \texttt{dp[k + 1][r]}\right)$$ Kết quả của bài toán là $\texttt{dp[1][n]}$. **Độ phức tạp.** $O(n^3)$