Problem: Given a string $s$ and a DFA $D$, compute the longest subsequence of $s$ such that the subsequence is accepted by $D$, or report that no such subsequence exists.

This problem has a runtime of $O(qn)$ where $q$ is the number of states of the DFA, and $n$ is the length of the string.

This problem is supposed to be solved using Dynamic Programming.

I'm not sure what I would memoize in this problem. Would the start and stop states for every subsequence we compute be memoized so that when we add another element into the subsequence, we use the memoized subsequence? I'm really not sure, and I'd appreciate any hints or ideas in this direction.

EDIT: My recurrence (I can't figure out how to get a lower bound than $O(2^n)$--

Consider the string to be $A[1 .. n]$. And consider the substring $A[1 .. i]$ for $i < n$. I know the length of the longest subsequence accepted by the DFA for this substring. Next, I consider the substring $A[1 .. i+1]$.

If this substring has a longer subsequence that is accepted by the DFA, the max value is updated. If not, the max value is kept the same. To figure out if the max value got updated, I have to search for all subsequences accepted by the DFA that have $A[i+1]$ included in them, as well as the entire substring $A[1 .. i+1]$.

This last thing can be memoized. That is, the end point of the entire substring $A[1 .. i]$ can be memoized. So when we need to check if $A[1 .. i+1]$ works, we just need to go to the next state after reading $A[i+1]$.

We can also memoize a lot of the earlier problems we solved. We memoize the pair (subsequence, end-state).

Here's an example: Consider the string $a_1a_2a_3a_4$.

$a_1$:
Takes $O(1)$ to check. Then memoize.

$a_1a_2$:
Check $a_2$. Takes $O(1)$. Then memoize.
Check $a_1a_2$. Takes $O(1)$ as checking $a_1$ was previously memoized. Then memoize.

$a_1a_2a_3$:
Check $a_3$: Takes $O(1)$. Then memoize.
Check $a_1a_3$, $a_2a_3$: takes $O(1)$ per check, as $a_1$, $a_2$ were previously memoized. Then memoize. Check $a_1a_2a_3$: Takes $O(1)$ as checking $a_1a_2$ was previous memoized.

$a_1a_2a_3a_4$:
Check $a_4$: Takes $O(1)$. Then memoize.
Check $a_1a_4$, $a_2a_4$, $a_3a_4$: takes $O(1)$ per check, as $a_1$, $a_2$, $a_3$ were previously memoized.
Check $a_1a_2a_4$, $a_1a_3a_4$, $a_2a_3a_4$: takes $O(1)$ per check, as $a_1a_2$, $a_1a_3$, $a_2a_3$ were previously memoized.
Check $a_1a_2a_3a_4$: takes $O(1)$ as $a_1a_2a_3$ was previously memoized.

Problem: Given a string $s$ and a DFA $D$, compute the longest subsequence of $s$ such that the subsequence is accepted by $D$, or report that no such subsequence exists.

This problem has a runtime of $O(qn)$ where $q$ is the number of states of the DFA, and $n$ is the length of the string.

This problem is supposed to be solved using Dynamic Programming.

I can't figure out how to get a bound lower than $O(2^n)$.

My recurrence (it's $O(2^n)$ with memoization) --

Consider the string to be $A[1 .. n]$. And consider the substring $A[1 .. i]$ for $i < n$. I know the length of the longest subsequence accepted by the DFA for this substring. Next, I consider the substring $A[1 .. i+1]$.

If this substring has a longer subsequence that is accepted by the DFA, the max value is updated. If not, the max value is kept the same. To figure out if the max value got updated, I have to search for all subsequences accepted by the DFA that have $A[i+1]$ included in them, as well as the entire substring $A[1 .. i+1]$.

This last thing can be memoized. That is, the end point of the entire substring $A[1 .. i]$ can be memoized. So when we need to check if $A[1 .. i+1]$ works, we just need to go to the next state after reading $A[i+1]$.

We can also memoize a lot of the earlier problems we solved. We memoize the pair (subsequence, end-state).

Here's an example: Consider the string $a_1a_2a_3a_4$.

$a_1$:
Takes $O(1)$ to check. Then memoize.

$a_1a_2$:
Check $a_2$. Takes $O(1)$. Then memoize.
Check $a_1a_2$. Takes $O(1)$ as checking $a_1$ was previously memoized. Then memoize.

$a_1a_2a_3$:
Check $a_3$: Takes $O(1)$. Then memoize.
Check $a_1a_3$, $a_2a_3$: takes $O(1)$ per check, as $a_1$, $a_2$ were previously memoized. Then memoize. Check $a_1a_2a_3$: Takes $O(1)$ as checking $a_1a_2$ was previous memoized.

$a_1a_2a_3a_4$:
Check $a_4$: Takes $O(1)$. Then memoize.
Check $a_1a_4$, $a_2a_4$, $a_3a_4$: takes $O(1)$ per check, as $a_1$, $a_2$, $a_3$ were previously memoized.
Check $a_1a_2a_4$, $a_1a_3a_4$, $a_2a_3a_4$: takes $O(1)$ per check, as $a_1a_2$, $a_1a_3$, $a_2a_3$ were previously memoized.
Check $a_1a_2a_3a_4$: takes $O(1)$ as $a_1a_2a_3$ was previously memoized.

Problem: Given a string $s$ and a DFA $D$, compute the longest subsequence of $s$ such that the subsequence is accepted by $D$, or report that no such subsequence exists.

This problem has a runtime of $O(qn)$ where $q$ is the number of states of the DFA, and $n$ is the length of the string.

This problem is supposed to be solved using Dynamic Programming.

I'm not sure what I would memoize in this problem. Would the start and stop states for every subsequence we compute be memoized so that when we add another element into the subsequence, we use the memoized subsequence? I'm really not sure, and I'd appreciate any hints or ideas in this direction.

Problem: Given a string $s$ and a DFA $D$, compute the longest subsequence of $s$ such that the subsequence is accepted by $D$, or report that no such subsequence exists.

This problem has a runtime of $O(qn)$ where $q$ is the number of states of the DFA, and $n$ is the length of the string.

This problem is supposed to be solved using Dynamic Programming.

I'm not sure what I would memoize in this problem. Would the start and stop states for every subsequence we compute be memoized so that when we add another element into the subsequence, we use the memoized subsequence? I'm really not sure, and I'd appreciate any hints or ideas in this direction.

EDIT: My recurrence (I can't figure out how to get a lower bound than $O(2^n)$--

Consider the string to be $A[1 .. n]$. And consider the substring $A[1 .. i]$ for $i < n$. I know the length of the longest subsequence accepted by the DFA for this substring. Next, I consider the substring $A[1 .. i+1]$.

If this substring has a longer subsequence that is accepted by the DFA, the max value is updated. If not, the max value is kept the same. To figure out if the max value got updated, I have to search for all subsequences accepted by the DFA that have $A[i+1]$ included in them, as well as the entire substring $A[1 .. i+1]$.

This last thing can be memoized. That is, the end point of the entire substring $A[1 .. i]$ can be memoized. So when we need to check if $A[1 .. i+1]$ works, we just need to go to the next state after reading $A[i+1]$.

We can also memoize a lot of the earlier problems we solved. We memoize the pair (subsequence, end-state).

Here's an example: Consider the string $a_1a_2a_3a_4$.

$a_1$:
Takes $O(1)$ to check. Then memoize.

$a_1a_2$:
Check $a_2$. Takes $O(1)$. Then memoize.
Check $a_1a_2$. Takes $O(1)$ as checking $a_1$ was previously memoized. Then memoize.

$a_1a_2a_3$:
Check $a_3$: Takes $O(1)$. Then memoize.
Check $a_1a_3$, $a_2a_3$: takes $O(1)$ per check, as $a_1$, $a_2$ were previously memoized. Then memoize. Check $a_1a_2a_3$: Takes $O(1)$ as checking $a_1a_2$ was previous memoized.

$a_1a_2a_3a_4$:
Check $a_4$: Takes $O(1)$. Then memoize.
Check $a_1a_4$, $a_2a_4$, $a_3a_4$: takes $O(1)$ per check, as $a_1$, $a_2$, $a_3$ were previously memoized.
Check $a_1a_2a_4$, $a_1a_3a_4$, $a_2a_3a_4$: takes $O(1)$ per check, as $a_1a_2$, $a_1a_3$, $a_2a_3$ were previously memoized.
Check $a_1a_2a_3a_4$: takes $O(1)$ as $a_1a_2a_3$ was previously memoized.