Dynamic Programming Algorithm Requirements

Question

To my knowledge, a problem can be solved using Dynamic Programming if it has the following two properties:

1. Overlapping Subproblems
2. Optimal Substructure (an optimal solution can be constructed efficiently from optimal solutions of its subproblems)

I have two questions:

1. Which kind algorithm should be used to solve a problem if it exhibits property 1, but not 2?
2. Similarly, which kind of algorithm should be used to solve a problem if it exhibits property 2, but not 1?

Some examples of problems would be very helpful too.

For example: The Fibonacci Sequence exhibits both properties and so you can use dynamic programming to efficiently find the nth value in the sequence.

Answer 1

I have an answer only for the first sub-question.

Overlapping subproblems but no optimal substructures

Addition chain exponentiation problem

An example of a problem with overlapping subproblems but no optimal substructures is the shortest addition-chain exponentiation problem, a method of exponentiation by a positive integer power that requires a minimal number of multiplications. For example, the shortest chain for $a^{15}$ requires only 5 multiplications since $a^{15} = a^{3}\times ([a^{3}]^2)^2$. The shortest chain for $a^6$ is 3 multiplications since $a^6 = ((a^2)^2)^2$.

However, this problem has no optimal substructures. In the shortest addition chain for $a^{15}$, the subproblem for $a^6$ can be optimally computed as $(a^3)^2$ by re-using $a^3$. The best solution is not found from $a^6 = ((a^2)^2)^2$ which requires three multiplies.

The problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for a15 above, the subproblem for a6 must be computed as (a3)2 since a3 is re-used (as opposed to, say, a6 = a2(a2)2, which also requires three multiplies).

Longest path problem

Another example is the longest path problem. Consider the graph below:

If the Longest Path problem has optimal subtructures, then the longest-path from A to C can be written as:

Longestpath(A, C) = Longest_path(A, D) + (DC)

The longest path from A to D is ABCD. However this solution cannot be used to solve for Longestpath(A, C) since the path DC repeats.

Choosing an algorithm for solving

Both problems mentioned above are NP-hard so no algorithm can solve it optimally. Such problems require approximations and randomized algorithms.

References

• https://en.wikipedia.org/wiki/Addition-chain_exponentiation#
• https://www.javatpoint.com/optimal-substructure-property