Dynamic Programming

We did lots of work in this space for certain kinds of business problems, following some new developments.   This kind of problem could in the future be addressed by Quantum Computing.   Technical:

Prof Patrick H. Madden  SUNY Binghamton   CSD  pmadden@acm.org, explanatory slides from talk last year:
   https://drive.google.com/open?id=1hKxS3R4t4B7DXlhhJwSWJutbmutWZ78-

and an introductory article that is unconnected with the above:

Dynamic Programming vs Divide-and-Conquer  Or Divide-and-Conquer on Steroids

In this article I’m trying to explain the difference/similarities between dynamic programing and divide and conquer approaches based on two examples: binary search and minimum edit distance (Levenshtein distance).

The Problem
When I started to learn algorithms it was hard for me to understand the main idea of dynamic programming (DP) and how it is different from divide-and-conquer (DC) approach. When it gets to comparing those two paradigms usually Fibonacci function comes to the rescue as great example. But when we’re trying to solve the same problem using both DP and DC approaches to explain each of them, it feels for me like we may lose valuable detail that might help to catch the difference faster. And these detail tells us that each technique serves best for different types of problems.

I’m still in the process of understanding DP and DC difference and I can’t say that I’ve fully grasped the concepts so far. But I hope this article will shed some extra light and help you to do another step of learning such valuable algorithm paradigms as dynamic programming and divide-and-conquer. ... 




Dynamic Programming and Divide-and-Conquer Similarities

As I see it for now I can say that dynamic programming is an extension of divide and conquer paradigm.

I would not treat them as something completely different. Because they both work by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

So why do we still have different paradigm names then and why I called dynamic programming an extension. It is because dynamic programming approach may be applied to the problem only if the problem has certain restrictions or prerequisites. And after that dynamic programming extends divide and conquer approach with memorization or tabulation technique.

Let’s go step by step… "