How is "dynamic" programming different than "normal" programming?

Question

Whenever I look at solutions to computer contests, I always see the term "dynamic programming". I Googled the term and read a few articles, but none of them provide a simple example of programming VS "dynamic" programming. So how is "dynamic" programming different than "normal" programming? (simple terms please!)

Answer 1

Dynamic Programming uses programming more in the sense used with Linear Programming -- a mechanism of solving a problem.

One description I recently read (but can no longer recall the source -- [citation needed]) suggested that the usual approach of divide and conquer used in recursion is a top-down approach to solving problems, while dynamic programming is a bottom-up approach to solving problems.

The Wikipedia article suggests computing the Fibonocci sequence is an excellent use of dynamic programming -- you memoize results as you compute them for further use in the algorithm, to avoid re-computing similar results.

Knuth's algorithm for line-breaking paragraphs is another good example of dynamic programming: if you consider the possibility of inserting line breaks between every word (and even breaking lines inside words, at hyphenation points), it feels like the only algorithms will be exponential -- or worse. However, by keeping track of the "badness" associated with previous line breaks, Knuth's algorithm actually runs in linear time with the size of the input. (I must admit that I don't fully understand Knuth's algorithm -- only that it is supremely clever.)

Answer 2

By "normal" programming, I think you mean C++/Java/C# programming, right?

Dynamic programming is not "programming" in that sense. It is not about writing code, but the word "programming" there is used in the context of solving complex problems by breaking them down into simpler problems.

Answer 3

Dynamic programming is not really 'programming' but table lookup [and storage] - That is sacrifice a bit of space to improve time complexity [quite a bit].

Answer 4

I knew this is an old post but I was having the same questions so I am answering myself here.

Dynamic programming has two properties:

1. Optimal substructure: a globally optimal solution can be found by combining optimal solutions to local subproblems. For example, fib(x) = fib(x - 1) + fib(x – 2)
2. Overlapping subproblems: finding an optimal solution involves solving the same problem multiple times. For example, compute fib(x) many times in Fibonocci sequence

By the above definition/properties, it is not clear whether certain questions like "Does an element belong to a set"? or "How to find the sum of a set" can be classified as dynamic programming? I can divide the set into subset (solve globally) and add it up (get global answer). Also, within the subset, I did the summation many times.

I found a paragraph in a book and I think it provides very helpful tips to distinguish "Dynamic Programming"(DP) and "Divide and conquer algorithm"(D&C).

1. In D&C subproblems, they are substantially smaller then the original problem. In contrast, DP involves solving problems that are only slightly smaller than the original problem. For example, computing Fib(19) is not a substantially smaller problem than computing Fib(20). While compute sum of ten elements is substantially smaller than sum of ten million elements.

2. Efficiency of D&C algorithms does not depend upon structuring the algorithm so that identical problems are solved repeatedly. In contrast, DP is efficient only when the number of distinct subproblems is significantly smaller than the total number of subproblems.