Overlapping Subproblems

AlgorithmsCoding A problem exhibits overlapping subproblems if the problem is solved by reusing solutions of subproblems multiple times. In the context of a computation DAG , this is equivalent to not being a tree.

A technique for designing subproblems when the problem data is a sequence is to consider the following sub-structures:

• Prefixes: x[:i] (1-D DP)
• Suffixes: x[i:] (1-D DP)
• Congruent subsequences: x[i:j] (2-D DP)

Memoization consists of storing the results of each solution for every or .