How to prove a Dynamic programming strategy will work for an algorithm?

Question

How can I prove that a dynamic programming (dp) strategy for a problem will work or not? For greedy algorithms, we can prove by showing the sub problems exhibits matroid property. Is there any such methods for dp algorithms?

Answer 1

In principle, any multi-stage optimization problem is solvable using dynamic programming, if you can come up with the right notion of the state. You do not mention which class of problems you are working on, so it hard to give general guidelines. I'll make the following assumptions here:

• You are looking at deterministic optimization problems (as opposed to stochastic optimization problems).
• You have to choose finite number of decisions, and in the end want to maximize rewards that depend on all your decisions (the argument also works if you are interested in minimizing costs).
• You can decompose the total reward into sum of individual rewards, ideally, in such a way that decision n influences the total reward for the first time only from the n-th term onwards.

In order to solve such a problem by dynamic programming, you need to come up with a state state_n that satisfies the following properties:

state_n+1 = function(state_n, decision_n)

and

reward_n = function(state_n, decision_n)

If these conditions are satisfied, then dynamic programming gives an optimal solution. First you define value functions

V_n(state_n) = max_decisionn[ reward_n + V_n+1(state_n+1)]

and recursively solve for these value functions in a backward manner.

NOTE: These are the simplest class of problems that can be solved using dynamic programming. For more details, see any standard book on dynamic programming, e.g., Berksekas.

Answer 2

In general, the Dynamic Programming solution can be proved by showing that your solution exhibits the Optimal Substructure property.

Basically, you formulate the actual problem as composed of smaller subproblems and then combine the solutions to get your final answer. In combining, if the problem size increases, then the solution for smaller subproblem must still be optimal for the combination to actually work.

For example, if in a graph you are trying to find an the shortest path between A and C, and you already know(somehow) that that path passes through an intermediate point B, and you already know the shortest way to get from A to B, then you only need to find a shortest way to get to C from B. You don't have to worry about finding a new way all the way from A to C, that's what the optimal substructure property means. For a dynamic programming correctness proof, proving this property is enough to show that your approach is correct.

They way you prove Greedy algorithm by showing it exhibits matroid structure is correct, but it does not always work. Some greedy algorithms will not show Matroid structure, yet they are correct Greedy algorithms. For example, Huffman encoding scheme is a greedy approach, but it does not exhibit matroid structure.

To prove a greedy algorithm, in general, you need to show that your solution exhibits -1) optimal substructure property as in DP and 2) The choice made by a greedy approach is not sub-optimal (basically show that it is optimal or one of the optimal choices that can be made at that point in time)