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.