# Can counting problems have optimal substructure?

I understand that for a problem to be solvable using dynamic programming, it needs to have the following properties:

1. optimal substructure
2. overlapping subproblems

I stumbled upon an article which states that:

Counting problems cannot exhibit optimal substructure, because they are not optimization problems. Instead, the kinds of counting problems that are amenable to DP solutions exhibit a different kind of substructure, which we shall term disjoint and exhaustive substructure.

Is this a valid claim? The Wikipedia article on Dynamic Programming states that:

In addition to finding optimal solutions to some problems, dynamic programming can also be used for counting the number of solutions...

This implies that counting problems can have optimal substructure. I'm confused about what the PEG article is trying to say. I've also been unable to find information on this concept of disjoint and exhaustive substructure. My guess is that PEG is being a bit pedantic and the concept of optimal substructure only makes sense in the context of optimisation problems. You can't have an optimal count, there is just one correct answer. By disjoint we mean that we're interested in subproblems where solutions don't overlap (in order to avoid duplicates, we only want to count each unique combination once) and exhaustive means we want to count all possible unique combinations.

I thought I have a reasonable understanding of dynamic programming but reading this has confused me so essentially I'm looking for clarification.

Edit: I've found another article on this which looks useful but I'm struggling to understand the proof provided for optimal substructure. I also can't find any information on what weak ordering has to do with dynamic programming and optimal substructure.

• The claim you're worried about isn't a formal claim. As such, it is a matter of opinion. For some people, the features that counting problems amenable to dynamic programming have constitute optimal substructure, others prefer to make a distinction here. If this claim confuses you, I suggest ignoring it. Commented Aug 3, 2017 at 18:33

I think you understand what's going on well. It's just two different ways of looking at things. I agree with you that I think PEG is being a bit pedantic. Personally, I never particularly liked "optimal substructure + overlapping subproblems" as the definition of dynamic programming; those are characteristics that dynamic programming algorithms tend to have, and tend to help us separate dynamic programming from (say) divide-and-conquer or greedy algorithms. I like to think of dynamic programming as recursion plus memoization (and possibly, plus table-driven bottom-up memoization). But to each their own.

• Are either of memoization or tabulation defining features of DP? It seems like a considerable amount of people treat DP and memoization as being synonymous (or at least that mem. or tab. is necessary) but that doesn't feel right. E.g. in Skiena 8.1.3 the fib_ultimate example is a DP solution but it doesn't use of memoization (which is just an optimisation technique and can be used in many contexts). Commented Aug 6, 2017 at 11:06
• @Izaan I think fib_ultimate is still using caching, its just been optimized to keeping only track of the last two values (instead 'tabulating' the values of fib 1 to n) as going bottom-up only requires a cache of the last two values. Commented Jun 13, 2022 at 15:40

One way of answering the question in the title is yes, you can always reduce a counting problem to a problem with suboptimal substructure, and thus counting would have suboptimal substructure in that reduced problem. Whether or not that reduction is useful and you end up with an asymptotically efficient algorithm is a different matter.