17
$\begingroup$

I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization.

Am I understanding correctly? Or is DP something else?

Improve this question
$\endgroup$
3
  • $\begingroup$ No, memorization is not the major part of Dynamic Programming (DP). Memorization could be considered as an auxiliary tool that often appears in DP. $\endgroup$
    – John L.
    Nov 2, 2018 at 19:13
  • $\begingroup$ Other name Dynamic tables $\endgroup$
    – kelalaka
    Nov 2, 2018 at 19:13
  • 1
    $\begingroup$ stackoverflow.com/questions/6184869/… $\endgroup$
    – Sanghyun Lee
    Aug 5, 2019 at 14:42

4 Answers 4

Reset to default
19
$\begingroup$

Summary: the memoization technique is a routine trick applied in dynamic programming (DP). In contrast, DP is mostly about finding the optimal substructure in overlapping subproblems and establishing recurrence relations.

Warning: a little dose of personal experience is included in this answer.

Reading suggestion: If this answer looks too long to you, just read the text in boldface.

Background and Definitions

Memoization means the optimization technique where you memorize previously computed results, which will be used whenever the same result will be needed.

Memoization comes from the word "memoize" or "memorize".

Dynamic programming (DP) means solving problems recursively by combining the solutions to similar smaller overlapping subproblems, usually using some kind of recurrence relations. (Some people may object to the usage of "overlapping" here. My definition is roughly taken from Wikipedia and Introduction to Algorithm by CLRS.) I will only talk about its usage in writing computer algorithms. Note that an actual implementation of DP might use iterative procedure.

Why is DP called DP? The word "dynamic" was chosen by its creator, Richard Bellman to capture the time-varying aspect of the problems, and because it sounded impressive. For the full story, check how Bellman named dynamic programming?.

Nowadays I would interpret "dynamic" as meaning "moving from smaller subproblems to bigger subproblems". (The word "programming" refers to the use of the method to find an optimal program, as in "linear programming". People like me treat it as in software programming sometimes.)

Explanations

Why do some people consider they are the same?

It is understandable that Dynamic Programming (DP) is seen as "just another name of memoization or any tricks utilizing memoization". When the examples and the problems presented initially have rather obvious subproblems and recurrence relations, the most advantage and important part of DP seems to be the impressive speedup by the memoization technique.

In fact, for some time, I had been inclined to equating DP to mostly memoization technique applied to recursive algorithms such as computation of Fibonacci sequence or the computation of how many ways one can go from the left bottom corner to the top right corner of a rectangle grid.

How are DP and memoization different?

The memoization technique is an auxiliary routine trick that improves the performance of DP (when it appears in DP). It appears so often and so effective that some people even claim that DP is memoization

Let me use a classic simple example of DP, the maximum subarray problem solved by Kadane's algorithm, to make the distinction between DP and memoization clear.

Since I was a kid, I had been wondering how I could find the maximum sum of a contiguous subarray of a given array. First thought was grouping adjacent positive numbers together and adjacent negative numbers together, which could simplify the input. Then I tried combine neighbouring numbers together if their sum is positive or, hm, negative. Then the uncertainty seemed attacking my approach from everywhere. Many years later, when I stumbled upon the Kadane's algorithm, I was awe-struck. It is such a beautiful simple algorithm, thanks to the simple but critical observation made by Kadane: any solution (i.e., any member of the set of solutions) will always have a last element. Trust me, only if you can appreciate the power of such a simple observation in the construction of DP can you fully appreciate the crux of DP.

Please note there is not any (significant) usage of memoization in Kadane's algorithm.

Just in case you might brush off Kadane's algorithm as being trivial, let me present two similar problems.

  • Can you find efficiently the maximum sum of two disjoint contiguous subarray of a given array of numbers?
  • Can you find efficiently two disjoint increasing subsequence of a given sequence of numbers the sum of whose lengths is the maximum?

If you can find the solution to these two problems, you will, I believe, be able to appreciate the importance of recognizing the subproblems and recurrence relations more. That might just be the start of a long journey, if you are like me.

By Wikepedia entry on Dynamic programming, the two key attributes that a problem must have in order for DP to be applicable are the optimal substructure and overlapping sub-problems. In other words, the crux of dynamic programming is to find the optimal substructure in overlapping subproblems, where it is relatively easier to solve a larger subproblem given the solutions of smaller subproblem.

In summary, here are the difference between DP and memoization.

  • DP is a solution strategy which asks you to find similar smaller subproblems so as to solve big subproblems. It usually includes recurrence relations and memoization.
  • Memoization is a technique to avoid repeated computation on the same problems. It is special form of caching that caches the values of a function based on its parameters.

More advanced dynamic programming

Here I would like to single out "more advanced" dynamic programming. More advanced is a pure subjective term. What I would like to emphasize is that the harder the problems become, the more difference you will appreciate between dynamic programming and memoization.

Even as the problem becomes harder and varied to solve, there is not much variation to the memoization. The memoization technique are present and helpful most of the time. However, it becomes routine. After all, all you need to do is just to record all result of subproblems that will be used to reach the result of final problem.

However, as I have been solving more and harder problems using DP, the task of identifying the subproblems and construction of the recurrence relations becoming more and more challenging and interesting. There are many variations and techniques in how you can recognize or define the subproblems and how to deduce or apply the recurrence relations. Many of the harder problems look like having a distinct personality to me. Here are some classical ones that I have used.

  • the More-Subproblems Principle (named by me for the lack of a name): when the recurrence relations cannot be established because the solutions to bigger subproblems need to use some condition that is not tracked by the solutions to smaller subproblems, extend the subproblems by another parameter (a.k.a. dimension) to keep track of that condition. The more refined subproblems have been solved, the easier to solve the bigger subproblems, even with the extra condition.

The following is a nice article.

Improve this answer
$\endgroup$
10
  • 2
    $\begingroup$ @Josh Good question. I mean, simply, every subarray has a last element. (Thus, an bigger array can be viewed as pushing the last element of a smaller array to the right. The index of the last element becomes a natural parameter that classifies all subarrays.) I want to emphasize the importance of identifying the right parameters that classify the subproblems. One remarkable characteristic of Kadane's algorithm is that although every subarray has two endpoints, it is enough to use one of them for parametrization. This brilliant breakage of symmetry strikes as unnatural from time to time. $\endgroup$
    – John L.
    Apr 20, 2020 at 22:28
  • 1
    $\begingroup$ Yes, basically. Each parameter used in the classification of subproblems means one dimension of the search. The dimension of the search may sound like a number, while the parametrization refers to how the dimensions come from. $\endgroup$
    – John L.
    Apr 20, 2020 at 22:58
  • 1
    $\begingroup$ The best way to explain to a 4 year-old what dynamic-programming might be this demonstration of the power of memoization. However, the essential part and "the hard part of dynamic programming is knowing what to memoize and how to apply it". $\endgroup$
    – John L.
    Apr 29, 2020 at 15:09
  • 1
    $\begingroup$ "finding the optimal substructure" could have been "recognizing/constructing the optimal substructure". The latter emphasizes that the optimal substructure might not obvious. $\endgroup$
    – John L.
    Apr 29, 2020 at 15:23
  • 2
    $\begingroup$ Since I was a kid, I had been wondering how I could find the maximum sum of a the contiguous subarray of a given array. - I too pondered these questions as a child /s $\endgroup$
    – alex
    May 17, 2021 at 19:05
5
$\begingroup$

Memoization is the technique to "remember" the result of a computation, and reuse it the next time instead of recomputing it, to save time. It does not care about the properties of the computations.

Dynamic programming is the research of finding an optimized plan to a problem through finding the best substructure of the problem for reusing the computation results. In other words, it is the research of how to use memoization to the greatest effect.

The name "dynamic programming" is an unfortunately misleading name necessitated by politics. The "programming" in "dynamic programming" is not the act of writing computer code, as many (including myself) had misunderstood it, but the act of making an optimized plan or decision.

The earlier answers are wrong to state that dynamic programming usually uses memoization. Dynamic programming always uses memoization. They make this mistake because they understand memoization in the narrow sense of "caching the results of function calls", not the broad sense of "caching the results of computations".

For example, let's examine Kadane's algorithm for finding the maximum of the sums of sub-arrays. The listing in Wikipedia is written in Python, reproduced below:

def max_subarray(numbers):
    """Find a contiguous subarray with the largest sum."""
    best_sum = 0  # or: float('-inf')
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

On first sight, this looks like it does not use memoization. That's only because memoization is implicit in the current_sum variable. If this variable is not used to memoize the intermediate results, then every previous current_sum needs to be computed again, and the algorithm does not save any time.

This point is more clear if we rewrite the code in a pure functional style:

max_subarray numbers = go 0 0 numbers
  where
    go best_sum _           []     = best_sum
    go best_sum current_sum (n:ns) =
         let current_sum' = max 0 (current_sum + n)
             best_sum' = max best_sum current_sum' 
         in go best_sum' current_sum' ns

Now, what if instead of current_sum being a parameter, it is a function that finds the maximum sum of all sub-arrays ending at that element?

max_subarray numbers = go 0 [] numbers
  where
    current_sum_f []          = 0
    current_sum_f (n:prev_ns) = max 0 (current_sum_f prev_ns + n)
    go best_sum prev_ns []     = best_sum
    go best_sum prev_ns (n:ns) =
         let best_sum' = max best_sum (current_sum_f (n:prev_ns))
         in go best_sum' (n:prev_ns) ns

In the rewrite above, current_sum_f is the computation actually representative of the sub-problem "finding the maximum sum of all sub-arrays ending at that element".

Without memoization, the algorithm is $O((1 + N) * N / 2)$ in time and $O(1)$ in space. Exactly the same as a naive algorithm searching through every sub-array.

With naive memoization, that is, we cache all intermediate computations, the algorithm is $O(N)$ in time and $O(N + 1)$ in space. Typical exchange of space for time.

But that's not Kadane's algorithm. Kadane's algorithm only memoizes the most recent computation. It is $O(N)$ in time and $O(2)$ in space. Why is that correct?

Because for current_sum_f, recurrence is only one step deep. If it is like generating Fibonacci sequence, which is two steps deep, then we need to memoize the two most recent computation.

References:

Read More:

Improve this answer
$\endgroup$
3
  • $\begingroup$ Welcome to Computer Science! A very-well written answer. It does make sense to conclude that dynamic programming always use memoization. On the other hand, it also make sense that almost all computer programs use memoization as long as they use memory repeatedly. $\endgroup$
    – John L.
    Mar 21, 2020 at 16:47
  • $\begingroup$ Ah yes! I should have generalized my thought even more. "Memoization", coming from the word "remember", surely is closely related to memory. I agree with you with two qualifications: 1) that the memory is repeatedly read without writes in between; 2) distinct from "cache", "memo" does not become invalid due to side effects. (with "caching" we "cache" value into a "cache", with "memoization" we "memoize" value into a "?", I propose "memo" but please tell me if there is established term) $\endgroup$
    – Yufan Lou
    Mar 21, 2020 at 19:52
  • $\begingroup$ The two qualifications are actually one, 2) can be derived from 1). Or if we approach from the essence that memoization associates a memo with the input producing it, both 1) and 2) are mandated by this essence. $\endgroup$
    – Yufan Lou
    Mar 21, 2020 at 20:01
1
$\begingroup$

In Memoization, you store the expensive function calls in a cache and call back from there if exist when needed again. This is a top-down approach, and it has extensive recursive calls.

In Dynamic Programming (Dynamic Tables), you break the complex problem into smaller problems and solve each of the problems once. In Dynamic Programming, you maintain a table from bottom up for the subproblems solution.

Both are applicable to problems with Overlapping sub-problems; as in Fibonacci sequence. If there is no overlapping sub-problems you will not get a benefit; as in the calculation of $n!$

The result can be solved in same $\mathcal(O)$-time in each. DP, however, can outperform the memoization due to recursive function calls. If the sub-problem space need not be solved completely, Memoization can be a better choice.

Improve this answer
$\endgroup$
1
$\begingroup$

From Wikipedia:

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead[1]. This is why merge sort and quick sort are not classified as dynamic programming problems.

Therefore, it seems the point is overlapping of subproblems. And if some subproblems are overlapped, you can reduce amount of processing by eliminating duplicated processing. There can be many techniques, but usually it's good enough to re-use operation result, and this reusing technique is memoization. I can imagine that in some cases of well designed processing paths, memoization won't be required.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.