How do you reason whether an exercise has a dynamic programming solution or not? If it has then how do you develop the algorithm to solve it?

What conditions does a programming problem need to meet in order to be solved trough dynamic programming? What reasoning do you do in order to find out?

Once you conclude that it indeed has a DP solution then how would you go on about creating a DP algorithm that solves it? What's the logic behind creating such algorithms?

Answers


A problem must meet two conditions in order to be solved trough dynamic programming. Citing Introduction to Algorithms, chapter 15:

Optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.

When a recursive algorithm revisits the same problem repeatedly, we say that the optimization problem has overlapping subproblems.

In The Algorithm Design Manual, chapter 8, the author describes the three steps involved in solving a problem by dynamic programming:

  1. Formulate the answer as a recurrence relation or recursive algorithm.
  2. Show that the number of different parameter values taken on by your recur- rence is bounded by a (hopefully small) polynomial.
  3. Specify an order of evaluation for the recurrence so the partial results you need are always available when you need them.

As usual, the wikipedia contains an extensive discussion on the topic, if you want to dig deeper.


Need Your Help

Defining const static that needs setting up at runtime

c++ class static

I'm making use of a class with a few utilities defined as static methods eg.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.