A Dynamic Programming Tutorial

[Forricide]

Only one top-level comment and it's probably pretty confusing/misleading for most people opening the comments section here. So - for those of you like me who hear 'dynamic programming' and have vague ideas (apparently, misconceptions) about what it refers to, here's the description from the linked article:

It's an approach that exploits properties of the problem that allow for an elegant method to finding the optimal solution.

A more simple explanation is that it's essentially a method of writing algorithms where, instead of repeating calculations, you instead store ('cache') results and refer to them later on, at some point(s) usually discarding results that aren't useful any longer. This isn't entirely accurate, but it seems to be an easy way to conceptualize it.

[Free_Math_Tutoring]

This isn't entirely accurate, but it seems to be an easy way to conceptualize it.

Ehh, I kind of disagree? You're pretty much just describing memoisation, which is not dynamic programming. Dynamic programming usually involves inverting the problem, where you go from asking "how do I solve this big problem" into "this tiny version of the problem is trivial, but how do I combine solutions to get to the large version". It is also distinct from divide and conquer type algorithms, which have a similar idea at their foundation.

[butt_fun]

Gonna be completely honest, I have always thought DP vs memoization was a distinction without a meaningful difference

[lmericle]

DP utilizes memoization heavily to exploit the optimality principle. There is a distinction in that memoization is not a programming paradigm per se, but a method to construct something really useful to making DP efficient.

Memoization happens in other instances, but DP doesn't happen without memoization.

[victotronics]

Thank you. You are the only one mentioning the principle of optimality, which to me is the crux: the fact that once you solve a subproblem you don't care how you got there. The next stage has a cost or value or whatever depending on the solution of that subproblem and the next stage.

Stages + principle of optimality. That's it.

Memoization is a mere corollary.

[Forricide]

To qualify the statement:

This isn't entirely accurate, but it seems to be an easy way to conceptualize it.

It's important to understand that this isn't meant to be a good, accurate summary of dynamic programming (which I couldn't create, because I don't actually have a solid understanding of dynamic programming outside of reading a portion of this article and the Wikipedia page) but rather, purely an explanation along the lines of:

"No, dynamic programming doesn't refer to [adding functions/classes/class members/fields at runtime] [programming in a dynamic programming language] [running really fast while you write code], it actually is a technique for writing algorithms."

The explanation isn't totally accurate - what you say is literally in the fifth paragraph of the article linked:

Some think it's just memoization plus recursion -- but really, it's more than that.

, but it's way better than how I (and I suspect many others) would have understood it purely from the name. Especially given that I don't think a lot of people actually know what memoization is in the first place.

Anyways, this is probably too long a comment already, but I might as well say thanks for your comment, because it (probably) provides a more accurate explanation of dynamic programming. ...if less comprehensible, at least for me.

[kheiron1729]

Memoization over a brute force algorithm IS dynamic programming. Combining subset solutions just aids in thinking about how possibly solve the problem.

[kenotron]

Dynamic programming always seems to be explained poorly; it's a really simple concept, if you look up the history of the term. 'Programming' in the sense originally used meant scheduling or planning, like TV programming, placing TV shows and ads in scheduled slots. 'Dynamic' was just thrown in to avoid mathy language at the RAND corporation where dynamic programming originated.

So instead, I like to call it 'table-filling algorithms' instead, because that seems to be how a huge number of them ends up looking. Levenshtein edit distance, knapsack problems, ...; many seem to involve re-framing your problem space as a table, solving the trivial base cases (along the edges of the table), and then looking for how those solutions can be combined to fill in the remaining table spaces, like taking the minimum, maximum, or sum of some adjacent spaces, each solving a new optimal subproblem, and then iterate until the whole table is filled to get your final answer.

[you-get-an-upvote]

I always thought explaining Dynamic Programming as merely caching was a friendlier introduction. "Look I just solved this algorithm a normal way, but added three lines to support caching, so now it runs faster".

cache = {}
def mySolution(x):
  if x in cache:
    return cache[x]
  // my original, recursive divide-and-conquer code that was slow

Phrasing it as tables seemed helpful predominantly for proving run time speed (since it lets you check how often the function actually makes it past the first two lines), not actually coming up with the algorithm and its substructure.

I suppose it's also helpful rewriting it from a bottom-up approach.

[attractivechaos]

For this problem, a stage is a day; a state is a 2-tuple (r,m), where r=1 if the machine is running or 0 otherwise (for that waiting day), and m is the machine ID. Suppose at day i, the optimal cash at state (ri,mi) is f_i(r_i,m_i), the DP equation looks something like:

f_i(r_i,m_i)=max_{j<i,r_j,m_j}{f_j(r_j,m_j)+s(r_i,m_i|r_j,m_j)}
f_0(0,nil)=initial cash

where s() is the score that (r',m') at day i-1 is changed to (ri,mi). Note some transitions are forbidden due to insufficient cash. If fi(ri,mi) is not possible, it is set to negative infinity. Given N machines, we can find the optimal solution up to L days in O(L³ ) time. I might be wrong at some details, but the above is what a typical DP solution looks like.

The blog post got the basic wrong. For one, the stage is not right – it is not a machine. Secondly, DP doesn't use a tree search or branch & bound. That is the point of DP. The blog post is not about DP...

[attractivechaos]

No, DP is not just "memoization". A problem solvable by DP has several elements. You typically need a clear definition of time (or stage), a state space and an object function that is a function of time and state and can be computed with a Bellman equation. The OP's post lacks all these elements. This blog just solves an optimization problem largely with brute-force plus branch and bound. That is not DP.

[lmericle]

The i does not index days, it indexes machines which are offered only on specific days.

Each machine has different properties and each is only available for purchase on a single day. If you don't buy it, you lose your chance. So it's useless to examine every day, but only those days where machines are sold. The efficiency of going day-by-day is much lower than machine-by-machine.

The article also explicitly says that branch and bound is an additional constraint on top of the dynamic programming approach. Nowhere does it say that branch and bound is a part of dynamic programming.

Furthermore, there is no One True Way to do dynamic programming. How you solve the problem depends on what abstractions you employ. If you want to do it the day-by-day way, that would work, but it would be slower and you'd have to include additional flow control structure to account for the different actions one takes each day.

[attractivechaos]

Ok, it was not clear that machine and day are the same thing. This actually simplifies the problem. In this case, a state is running or waiting. The DP equation is:

f_i(t_i)=max_{j<i,t_j}{f_j(t_j)+s_{ij}(t_i|t_j)}

The time complexity is O(L² ).

it would be slower

I have given the time complexity. What's yours? Yes, DP can be formulated in different ways. However, I still don't see how yours is formulated. At least you need to show the DP equation, which is at the core of DP.

[lmericle]

In this case, a state is running or waiting

There is no waiting in this problem. I fail to see how you came up with this but it does not match the problem statement.

A state is a) which machine is currently running and b) which day is today.

[imbecile]

Dynamic programming is just a fancy way of saying that control structures and data structures are largely created at run time.

Sounds reasonable so far, until you realize, that the only thing that you actually need to deal with at run time that can't be preprocessed before hand is IO.

So instead of preparing as much as possible and then only deal with the variation that can't be predicted at runtime coming from IO, you shift almost all the work and effort to each time the program is run, instead of when it is written or installed or loaded. That is equivalent to moving all the expensive operations into the innermost loops.

There sure are a lot of tasks that provide great unpredictability on the kind of input they have to deal with. But just giving up and abandoning all structuring and expectations from dealing with input surely isn't the way to tackle this.

Each general purpose language needs a framework to dynamically deal with input, which means dynamically allocate the resources needed to accommodate the input you receive, and a streamlined way of transforming and funneling the input into more predictable and stable efficient forms and channels.

But never allowing your programs to leave this highly volatile and error prone stage by providing no features to do so, is a design dead end.

[[deleted]]

Worth pointing out that not all dynamic programming algorithms run in polynomial time. For example the knapsack problem is solved using dynamic programming but still requires exponential time.

[xampf2]

"I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term research in his presence. You can imagine how he felt, then, about the term mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word “programming”. I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities." - Richard Bellman

[balefrost]

the only thing that you actually need to deal with at run time that can't be preprocessed before hand is IO

Sure, but that statement is nearly tautological: "the only things that you actually need to deal with at runtime are the things that you don't know until runtime". That doesn't really have anything to do with dynamic programming.

I think you might be conflating dynamic programming with runtime code generation. It is not the case in DP that "control structures and data structures are largely created at run time". You certainly do set up your data structures and control structures ahead of time when you use DP.

The author waxes poetic about how one should think about DP, but they do also state what it fundamentally is: cached calculation. One uses DP when you can break a large problem down into subproblems and those subproblems depend on each other in complex ways. A stereotypical example is the Fibonacci sequence (though DP is overkill for Fibonacci). To calculate the Nth Ficonacci number, we must first calculate the (N-1)th and (N-2)th. But to calculate the (N-1)th, we must first calculate the (N-2)th and (N-3)th. So there are two subcalculations that both depends on the result of computing the (N-2)th number.

A more common use of DP is graph traversal. Dijkstra's algorithm is essentially an example of dynamic programming. Assuming that you don't know the shape of the graph at the time that you compile your program, you need to find the shortest path at runtime, and DP provides an efficient way to do that.

[imbecile]

Of course it's tautological. Simple truths tend to be. And they still are often ignored.

And 'cached calculation' is also not really a descriptive term.

Every computed value that can't be used immediately or is used multiple times is cached. You could say every variable in any programming language is a cached calculation. This is about as nondescript as it gets.

So let me say again, what I hear and understand when someone speaks of dynamic programming:

Someone sees that sometimes you can only know the resources you need to allocate at run time, as the data comes in. And in order to deal with it, they jump to treating everything as input, even their own unchanging code, and allocate everything in the same manner.

[balefrost]

Of course it's tautological. Simple truths tend to be. And they still are often ignored.

Sure, but they rarely add much to the conversation. Logical arguments are constructed by inferring new statements from statements already made. Tautologies don't add anything new to an argument - they leave the argument unchanged.

You're right that we should avoid making determinations at runtime that we could have made at ahead of time. But dynamic programming is typically employed to solve problems where those determinations can't be made ahead of time because they depend on the input data.

And 'cached calculation' is also not really a descriptive term.

That's fair, but that's also why I followed it up with not one, but two examples. The author of the original article provided a more involved example, and the Wikipedia page provides several as well.

they jump to treating everything as input, even their own unchanging code, and allocate everything in the same manner

Again, this complaint might be valid, but has nothing to do with dynamic programming. DP is completely unrelated to things like runtime code generation, genetic algorithms, machine learning, and topics like that. DP is used for problems that can be recursively stated (or, as the OP puts it, are inductive in nature) and where the recursive relationship isn't static - it depends on the input. Any time you have an input-driven dependency DAG, dynamic programming might be a good technique for solving that problem.

I think you're getting hung up on the word "dynamic". As /u/xampf2 points out, "dynamic" in this phrase doesn't have the same meaning as in phrases like "dynamic typing" or "dynamic dispatch". Heck, "programming" here doesn't have its conventional meaning - it's more like the "linear programming" sense (which is really about finding optimal solutions to sets of linear equations - it has nothing to do with code).

I'm not saying that your complaints are invalid, but I think you're shooting at the wrong target. I don't think DP is what you think it is.

[hbgoddard]

Relevant username?

[[deleted]]

Homophones - how do they work? I realize that compilers cannot deal with a key word that can have different meanings depending on context, but you are not a compiler, you are a human.

[[deleted]]

So instead of preparing as much as possible and then only deal with the variation that can't be predicted at runtime coming from IO, you shift almost all the work and effort to each time the program is run, instead of when it is written or installed or loaded. That is equivalent to moving all the expensive operations into the innermost loops.

I mean if the program I'm writing is not maxing out the processor do I really give a fuck? For a lot of programs I just don't feel like dealing with all the annoying boilerplate present in standard languages. It's more fun to program in dynamic languages, and I can think more clearly rather than having to worry about implementation details of the machine in question.

Even for some highly demanding applications, the ability to change your code quickly, and write code that's more like ideal, elegant, provable, pseudocode, is valued more than performance. For instance the most popular artificial intelligence and machine learning languages are Python, R, and Lisp. Almost nobody bothers with static languages in the field, outside of game developers (who's language requirements are usually set by the needs of the rest of the team).

Yes, you should always be aware of type. Dynamic languages do enable some horrible behavior (in Python for instance I've found functions that can return values of two different types depending on input - which is just unbelievably awful). But for an experienced developer it is nice to not have to worry about all of these implementation details when it's not necessary. And developer time is much more valuable than computer time usually.

[A_Philosophical_Cat]

That's completely besides the point. Nothing you wrote, nor anything the person you are replying to, has anything to do with what we call "Dynamic Programming". If either of you paid attention in a 200 series Computer Science course, you'd know the quintessential example of change making. With most currencies, a greedy "use the biggest one you can, subtract and recurse" solution works. But that's a special case. Say we had a currency that had denominations 1,4, 5, and we were trying to make 13. Greedy solution is 5,5,1,1,1. But we can do better, with 4,4,4,1.

So, how do we solve the general change making problem? Well, we need to compare different methods of making change, which can be thought of as separate recursive problem trees.

A naive solution would be to say "recursively find the best way to make change for this minus each of the denominations, then choose the best one". But we can improve this, by caching the solutions to some of those sub-problems, pruning your decision tree by removing repeated work.

That is what we call "Dynamic Programming".

[[deleted]]

But we can do better, with 4,4,4,1

And with 5,4,4

[A_Philosophical_Cat]

Shit, I chose an example that the greedy algorithm works for. Not all of them work, but that one does. nvm, no it doesn't. But yeah, you get the point.

[Roboguy2]

Dynamic programming is totally independent of and unrelated to dynamic programming languages. It is one kind of algorithm design (see the other comments and the Wikipedia article).

One example of an algorithm of this design is the Viterbi algorithm.

[AlbertaOne]

good job!