I've always been told that a problem must have the following two properties in order for it to be solvable using dynamic programming:

• optimal substructure
• overlapping subproblems

I'm currently reading up on the counting variant of coin change problem (that's where you need to work out all possible combinations of coins that add up to a particular number S) and there exists an algorithm that uses dynamic programming for solving this problem but I can't work out whether or not an optimal substructure exists for this problem. On PEGWiki, it says 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.

I'm having a hard time finding any literature on disjoint and exhaustive substructure so my first question is... What exactly is disjoint and exhaustive substructure and where can I find more information on this? My guess is that by disjoint we're saying that we want subproblems that don't contain common combinations, and by exhaustive we mean that all together we want to cover all combinations.

Again on PEGWiki:

The counting problem is more subtle. We cannot approach it in quite the same way as we approach the optimization problem, because the counting problem does not exhibit disjoint substructure when it is "sliced" this way.

So does this mean that it is still possible to use dynamic programming if there is no optimal substructure? Or am I missing something? I've considered that perhaps dynamic programming doesn't make sense in the context of counting problems but Wikipedia confirms that DP is applicable to counting problems:

In addition to finding optimal solutions to some problems, dynamic programming can also be used for counting the number of solutions, for example counting the number of ways a certain amount of change can be made from a given collection of coins, or counting the number of optimal solutions to the coin change problem described above.