Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top