What’s the insight into fuzzy regular expression matching that I’m missing? Unlike most DP problems I can’t see the “reoccurring subproblem.”
Even if we omit the + and * operators, we can still have an exponential number of possible matches (2^n or worse) but it’s not clear to me how solving an earlier subset of a regex allows you to skip additional work later.
Once you add in the + and * operators, of course, the size of the pattern you’re matching against is effectively infinite, though of course in practice you can bound it at the size of the string you’re matching. But you’ll still have an exponential number of combinations to search through.
