5
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Aug 3, 2017 at 18:33

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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). $\endgroup$
    – Izaan
    Aug 6, 2017 at 11:06
  • 1
    $\begingroup$ @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. $\endgroup$
    – worbel
    Jun 13, 2022 at 15:40
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.