patternMinor
Memoization without array
Viewed 0 times
arraywithoutmemoization
Problem
In Cormen et al.'s Introduction to algorithms, section 15.3 Elements of dynamic programming explains memoization as follow:
A memoized recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered as the recursive algorithm unfolds, its solution is computed and then stored in the table. Each subsequent time that we encounter this subproblem, we simply look up the value stored in the table and return it.
And it adds, as a footnote:
This approach presupposes that we know the set of all possible subproblem parameters and that we have established the relationship between table positions and subproblems. Another, more general, approach is to memoize by using hashing with the subproblem parameters as keys.
Is there any well-know DP problems that requires (or makes it easier) to store memoized values in a dictionary rather than in a (multi dimensional)array?
Background: if this is of any use, the reason for this question is that I'm trying to motivate the notion of (self-balanced) binary search trees to people that has just seen dynamic programming.
A memoized recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered as the recursive algorithm unfolds, its solution is computed and then stored in the table. Each subsequent time that we encounter this subproblem, we simply look up the value stored in the table and return it.
And it adds, as a footnote:
This approach presupposes that we know the set of all possible subproblem parameters and that we have established the relationship between table positions and subproblems. Another, more general, approach is to memoize by using hashing with the subproblem parameters as keys.
Is there any well-know DP problems that requires (or makes it easier) to store memoized values in a dictionary rather than in a (multi dimensional)array?
Background: if this is of any use, the reason for this question is that I'm trying to motivate the notion of (self-balanced) binary search trees to people that has just seen dynamic programming.
Solution
There are probably better examples, but here is one, off the top of my head:
Let's say you want to check whether the edit distance between two strings $S,T$ is $\le d$, and if it is, compute the edit distance. You can use the standard dynamic programming algorithm to compute the edit distance, but "prune" the computation (stop the recursion) at any place where the edit distance is known to be $>d$. This means you probably won't need to fill in the entire table; you'll only need to fill in some of the entries. Thus, using a dictionary can give a performance boost.
Let's say you want to check whether the edit distance between two strings $S,T$ is $\le d$, and if it is, compute the edit distance. You can use the standard dynamic programming algorithm to compute the edit distance, but "prune" the computation (stop the recursion) at any place where the edit distance is known to be $>d$. This means you probably won't need to fill in the entire table; you'll only need to fill in some of the entries. Thus, using a dictionary can give a performance boost.
Context
StackExchange Computer Science Q#66274, answer score: 5
Revisions (0)
No revisions yet.