Dynamic Programming(1) - Let's make it simple! (Learning After a/A)

Before getting started...

Dynamic Programming, also called DP, is always something people talk about when they're on their Leetcode march. I talked with some instructors in a/A (a couple of months ago when I was in mod 2), and found that DP is so hot a topic because:

1. It solves a lot of optimization problems.
2. It frequently gives better performance (smaller time complexity).
3. IT IS HARD TO UNDERSTAND!!

Yeah, I've also been trapped by the concept of "DP" frequently since I first heard this word. I admit, that it is hard to understand. However, when I see this paragraph on the wiki page of DP. In short, according to R. Bellman, this name was to some extent "fabricated", since other names like "decision research" might annoy the military.

Thus, there's one thing we have to clarify: this "Programming" in DP, doesn't mean the action that we're sitting beside a laptop, typing lines of code and being bothered with the bugs we just created... The word "Programming" should be comprehended from a mathematical aspect, which means "decision-making".

Decision-making?

Yeah, decision-making, just like the action each brain takes 35,000 times per day. However, it is more than that - don't forget the word "Dynamic". The "Dynamic" tells us that, this decision wasn't made immediately, like I just decided to grab my bottle for about 100ml water; on the contrary, it was made "multistaged".

Sometimes a human needs to make a decision, like Jerry is thinking about giving Morty $0.32. However, it is (usually) impossible for Jerry to give Morty one coin of $0.32 (rant: it looks like something Jerry might try...), while he has to think how to pile up changes for this value - a quarter + a nickel + 2 cents, or 3 dimes + 2 cents, etc.

Okay, now we know how to give Morty $0.32. How about 0.33$?

You'll get the answer very quickly - just add another cent to the previous solution(s)!

Right, good job! That's how "Dynamic" works - you know that 0.33$ is just one cent more than $0.32, and you've already got how to give 0.32$ to Morty. You have a solution for a complex problem, and now you are asked to solve another problem, which is just one step/one number/one coin further than the previous one - so you could come up with the answer based on its "predecessor stage".

I really love the explanation for DP in the top answer to this Quora question:

How should I explain dynamic programming to a 4-year-old?

Okay, now let's dive deeper...

Could anyone remember the first problem we could solve with DP in a/A?

Well, actually at the very beginning, this problem was used for introducing Recursion... (hope that my memory works well, tell me if I'm wrong here XD)

And then, we found it takes too much time when the input is a "not that big" number, like 45...

In order to solve it, we add a "memo variable" to the parameters...

Try, try to remember it...

Yes! The "Fibonacci" problem!

(Normally I'm not particularly eager to introduce DP with this problem, but for a/A graduates and students, this problem is better than others since we had a similar schedule in mod2. I'll explain why personally it's not my best choice for explaining DP later.)

So for the Fibonacci problem, our purpose is to find out the n-th number in a Fibonacci sequence. For the i-th number Fib[i], we will always have the equation, that Fib[i] = Fib[i-1] + Fib[i-2].

Before really solving this problem, let's clarify the "Characteristics" of DP:

1. States

It means the solution for an "earlier problem", which generally means the solution for a smaller number than the input. For many problems, it will be the optimized solution for that "smaller problem" (not including the Fibonacci problem since it's not an optimization thing, that's the reason why I said I do not normally choose it.)

So defining the "state" is the first and most important step for DP problems, since we could not DP it without this definition (next part). For example, in the Fibonacci problem, one "state" is one number in the Fibonacci sequence. The solution for Fib[i-2], is an "earlier" problem than Fib[i-1] and Fib[i], since Fib[i] and Fib[i-1] will rely on the solution of Fib[2], and then we could talk about the next point: state transition.

2. State Definition and Transition

How could we get one state based on the earlier state(s)? This is another thing that should be considered when defining the states. Yeah, sometimes we could find more than one definition that works, but we will always want the one with more apparent transition logic, and better time/space performance. So we might know that most DP problems could be transferred to a graph problem, but trust me, normally none of us will define the state as any kind of graph, since neither the transition nor time/space looks good... That's why for a lot of problems we will just define the state based on what we want to return.

For example, for the Fibonacci problem, we want to return Fib[n], so we could just define the i-th state as Fib[i], and the transition also looks good here: Fib[i] = Fib[i-1] + Fib[i-2]. Here we can see the transition works: we can get one state Fib[i] based on the earlier states Fib[i-1] and Fib[i-2] with some operation - in other words, that's how we are "transitioning" from earlier states to our expected state.

And, we usually will also have a habit, of calculating the earlier states first, then the following states... because it will be easier for us to know the very early state (like Fib[1] and Fib[2]), and when we reach a late state, we've already got the solution it is based on, and, the next point, it won't change.

3. "No aftereffect from how we solve it"

The calculation process of one state and its earlier states, has no aftereffect, on the late states. You might see a lot of articles suggesting this point of DP (in many languages). Other words for this point might be "The future is not related to the process of the past". In DP problems, when we reach a state, all of its earlier states won't be changed. Also, we'll only use the solution of the earlier state(s), but we don't have to care how we got the solution previously.

For example, when we are calculating Fib[10], based on the logic I mentioned in point 2, we've already got the solution (value) of Fib[9] and Fib[8], and we know the transition equation is Fib[10] = Fib[9] + Fib[8]. So now let's think about the following questions:

• What do we need for Fib[10]? - Just the value of Fib[9] and Fib[8].
• Will they change now, or after that when we are calculating Fib[11], Fib[12]...? - No, Fib[9] and Fib[8] have already been fully calculated, so there's no way to change them. Similarly, the value we used for calculating Fib[9], Fib[8], and the earlier states won't change anymore.
• Do we need to know how we calculated Fib[9] and Fib[8] when we are calculating Fib[10]? - Actually we know that, but do we have to? The answer is NO. If now someone tells us the value of Fib[9] and Fib[8] without telling us how they calculated them, and asks us for the value of Fib[10], it won't be any trouble - because the values are already enough for us to get Fib[10]!

Wrap up

Now we know the characteristics of DP. Actually it is also the approaches with which we could find out whether one problem can be solved by DP:

1. If it is state-able, which means we could understand it with step-by-step stages
2. We know the transition of states, which means that the way to solving a stage based on the earlier stage(s) is clear;
3. And when one stage is calculated, there is no way for it to influence the following states.

And the last thing, remember to record the early states - otherwise, we are calculating them repeatedly, and it's not DP at all!

Okay, now let's have a try...

So now we could see how DP is solving the Fibonacci problem: return the value of the n-th element in the Fibonacci Sequence. Let's try it step by step:

First, what's the state? As I mentioned above, the first thing we could consider is "what we finally want to return". So what do we want to return for this problem? The value of Fib[n]. So we could say the i-th state is the value of Fib[i].

Second, is the transition relationship clear? Yes, anyone who knows the Fibonacci sequence will say Fib[i] = Fib[i-1] + Fib[i-2], so the value of Fib[i] looks good for a state definition!

Third, calculate from the Fib[1] to Fib[n]. You'll suggest a loop or a recursion for this, but let's see the detail of iterations:

• Fib[1] and Fib[2] - the first two elements of a Fibonacci sequence are both one, based on the meaning of "Fibonacci".
• Fib[3] - Fib[1] + Fib[2] and we've already got their value from the previous steps(stages).
• Fib[4] - Fib[2] + Fib[3] and we've already got their value...
• Fib[5] - Fib[3] + Fib[4] and we've already...
• Fib[6] - Fib[5] + Fib[4] and ...
• ..........
• Finally, Fib[n] - Fib[n-1] + Fib[n-2], and yes, the values are already calculated!

So this is what will happen if we use DP to solve the Fibonacci problem. When we know these steps, it will be easier for us to write the code of it. So now, open your VSCode, create a new file, and try to write a function solving the Fibonacci problem, to make sure you are clear with this!

Yeah! The studying of DP is... finished?

I'm sorry, but not yet. Fibonacci is the most straightforward problem with DP, and just like I mentioned, I usually don't choose it as the problem for explaining DP, because with it, it's hard for me to introduce another characteristic of DP:

The Optimized Sub-Structure!

But I know introducing all about DP in one article will be overwhelming for both of you and me (I have to write too much then...) So, in my next article, I'll introduce this point of DP with another example I mentioned above:

The Coin Change Problem!

So, remember to add comments if you have questions about any paragraphs/sentences/words/alphabets in this article. And after that, please expect the next part of DP:

"Dynamic Programming(2) - Leetcode 322 Coin Change and Diving Deeper!"