# 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. Aug 3, 2017 at 18:33

• @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. Jun 13 at 15:40