a bit of string dp: Codeforces Round #272 Problem E (Div. 2)

Problem Statement:
Codeforces - 476E

Summary:
Given a string \(s\) and a pattern \(p\). Denote \(S_k\) as the set of strings produced from removing exactly \(k\) letters from \(s\). For each \(w \in S_k\), we define occurrences of \(p\) in \(w\) as the maximum number of non-overlapping substrings of \(w\) that match \(p\) exactly. Then our task is, for each \(k \leq |s|\) output the maximum occurrences of \(p\) amongst all \(w \in S_k\).
\(|s| \leq 2000, |p| \leq 500\)

Solution:
Firstly, suppose that we are considering the [i .. \(|s|\)] part of the string s. If we denote next[i] as the index immediately next to the end of a minimum length subsequence in [i .. \(|s|\)] that matches p. We also denote cost[i] as the number of letters that must be skipped (or deleted) in order to complete that subsequence. Then we have the following recursive relationship:
Denote L(i, k) be the maximum occurrences of pattern p in a substring [i .. \(|s|\)] after deleting exactly \(k\) letters. Then
L(i, k) = max { L(i+1, k), L(next[i], k - cost[i]) }
Our answers would be on L(0, k) for all the required k values.