Didn't think about edge cases before the first submission. Missed that could have a gap between \(i\) and the start of the longest valid parentheses which could make impossible to combine them.
Though about defining dfs(i) as the longest valid subsequence, but implemented as the longest valid subsequence starting on i or any position after that.
It was easier to think about the recursion after having is_open and is_close.
I didn't notice that the transition function could land on Kleene star pattern: s=aa and p=ab*a. In this case, transition(0)=[1,3] instead of just [1]. I received 3 wrong answers while fixing this bug. I found that creating functions like is_zero_or_more and expand were vital to continue to improve the solution.
I saw that plain recursion would result in exponential algorithm and didn't even considered trying to apply Dynamic Programming.
Takeaways
Check for Dynamic Programming even against your intuition. If both solution have the same time complexity, implement the easy one during the competition and both while studying.
Try to create small examples that exercises all possible transitions when working with Regular Expression problems.