The time-complexity of dynamic-programming with memoization
Here is the simple principle. Suppose an algorithm
- applies dynamic programming to solve a problem,
- with the majority of running time spent on computing $O(s)$ subproblems for some expression $s$,
- where each subproblem is computed/solved only once thanks to memoization,
- and it takes $O(u)$ time for some expression $u$ to compute/solve each subproblem, assuming it takes $O(1)$ time to access the result of any other subproblems that are needed during that computation,
then the time-complexity of the algorithm is $O(su)$, in general.
Analysis of the algorithm in the question
Let us estimate how many line-executions are done if the algorithm is run upon an input of a string of length $m$ and a pattern of length $n$.
There are $(m+1)(n+1)$ entries in the table dp (which represent $O(mn)$ subproblems). The code that actually computes and updates the entries are the code block from line $7$ to line $17$. Because of memoization, these lines will be executed at most once for each entry. So these $17-7+1$ lines will be executed at most $(m+1)(n+1)$ times, i.e., these lines correspond to at most $(17-7+1)(m+1)(n+1)$ line-executions.
How many times will line $4$ (for building and quitting calling stack frames), line $5$ and $6$ be executed? Except the first time that is triggered by line $2$, the execution of them is triggered by the execution of any one of $4$ lines, line $9$, $10$, $12$, or $15$, which happens during the execution of the code block mentioned above. So line $4$, $5$ and $6$ are executed at most $1 + 4(m+1)(n+1)$ times, i.e., these $3$ lines correspond to at most $3(1 + 4(m+1)(n+1))$ line-executions.
So, the total number of line-executions is at most $$(17-7+1)(m+1)(n+1) + 3(1 + 4(m+1)(n+1)) + 2,$$ where the last number $2$ is for the one-time execution of line $1$ and $2$ at the start of running the algorithm. We can check that it takes $O(1)$ time to execute each line, except for possibly line $2$, which is executed once that costs up to $O(mn)$ time. Hence, the time-complexity of the algorithm is $O(mn)$.
The analysis above serves as an example to illustrate and validate the principle.
Or we can apply the principle directly. There are $O(mn)$ subproblems. It takes $O(1)$ time to solve each subproblem, considering all recursive calls as taking $O(1)$ time. Hence the time-complexity of the total algorithm is $O(mn\times 1) = O(mn)$.