Introduction to Dynamic Programming with Examples

This article introduces dynamic programming and provides two examples with DEMO code: text justification & finding the shortest path in a weighted directed acyclic graph.

Two points below won’t be covered in this article(potentially for later blogs 😝):
1. Solutions(such as the greedy algorithm) that better suited than dynamic programming in some cases.
2. Situations(such as finding the longest simple path in a graph) that dynamic programming cannot be applied.

Introduction

Dynamic programming is a methodology(same as divide-and-conquer) that often yield polynomial time algorithms; it solves problems by combining the results of solved overlapping subproblems.
To understand what the two last words ^ mean, let’s start with the maybe most popular example when it comes to dynamic programming — calculate Fibonacci numbers.

Fibonacci numbers are number that following fibonacci sequence, starting form the basic cases F(1) = 1(some references mention F(1) as 0), F(2) = 1. F(n) = F(n-1) + F(n-2) for n larger than 2.

To calculate F(n) for a giving n:
What’re the subproblems?
Solving the F(i) for positive number i smaller than n, F(6) for example, solves subproblems as the image below.

What’re the overlapping subproblems?
From the previous image, there are some subproblems being calculated multiple times. By caching the results, we make solving the same subproblem the second time effortless.

There are two ways for solving subproblems while caching the results:
Top-down approach: start with the original problem(F(n) in this case), and recursively solving smaller and smaller cases(F(i)) until we have all the ingredient to the original problem.
Bottom-up approach: start with the basic cases(F(1) and F(2) in this case), and solving larger and larger cases.

The DEMO below(JavaScript) includes both approaches.
It doesn’t take maximum integer precision for javascript into consideration, thanks Tino Calancha reminds me, you can refer his comment for more, we can solve the precision problem with BigInt, as ruleset pointed out.

ruleset pointed out(thanks) a more memory efficient solution for the bottom-up approach, please check out his comment for more.

Let’s solve two more problems by following “Observing what the subproblems are” -> “Solving the subproblems” -> “Assembling the final result”.

Text Justification

Giving a paragraph, assuming no word in the paragraph has more characters than what a single line can hold, how to optimally justify the words so that different lines look like have a similar length?

Paragraph below is what I randomly picked:

In computer science, mathematics, management science, economics and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of (it is hoped) a modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.) The technique of storing solutions to subproblems instead of recomputing them is called “memoization”.

Let’s define a line can hold 90 characters(including white spaces) at most.

If we simply put each line as many characters as possible and recursively do the same process for the next lines, the image below is the result:

The function below calculates the “badness” of the justification result, giving that each line’s capacity is 90:
calcBadness = (line) => line.length <= 90 ? Math.pow(90 — line.length, 2) : Number.MAX_VALUE;
Why diff²? Because there are more punishments for “an empty line with a full line” than “two half-filled lines.”
Also, if a line overflows, we treat it as infinite bad.

The total badness score for the previous brute-force solution is 5022, let’s use dynamic programming to make a better result!

What’re the subproblems?
For every positive number i smaller than words.length, if we treat words[i] as the starting word of a new line, what’s the minimal badness score?

How to solve the subproblems?
The total badness score for words which index bigger or equal to i is calcBadness(the-line-start-at-words[i]) + the-total-badness-score-of-the-next-lines. We can make different choices about what words contained in a line, and choose the best one as the solution to the subproblem.

Let’s take a look at an example: if we have three words length at 80, 40, 30.
Let’s treat the best justification result for words which index bigger or equal to i as S[i].

What’s S[2]? We can make one choice:
Put a word length 30 on a single line -> score: 3600.

What’s S[1]? We can make two choices:
1. Putting the last two words on the same line -> score: 361.
2. Putting the last two words on different lines -> score: 2500 + S[2]
Choice 1 is better so S[2] = 361.

What’s S[0]? We can make three choices:
1. Putting the three words on the same line -> score: MAX_VALUE.
2. Putting the first word on line 1, and rely on S[1] -> score: 100 + S[1]
3. Putting the first two words on line 1, and rely on S[2] -> score: MAX_VALUE. + S[2]
Choice 2 is the best.

We can draw the dependency graph similar to the Fibonacci numbers’ one:

How to get the final result?
As long as we solved all the subproblems, we can combine the final result same as solving any subproblem.

The DEMO below is my implementation; it uses the bottom-up approach.
The memo table saves two numbers for each slot; one is the total badness score, another is the starting word index for the next new line so we can construct the justified paragraph after the process.

The image below is the justification result; its total badness score is 1156, much better than the previous 5022.

Finding the Shortest Path in Weighted Directed Acyclic Graph

For the graph above, starting with vertex 1, what’re the shortest paths(the path which edges weight summation is minimal) to vertex 2, 3, 4 and 5?

Before we go through the dynamic programming process, let’s represent this graph in an edge array, which is an array of [sourceVertex, destVertex, weight].

const edges = [
  [1, 4, 3], [1, 3, 6],
  [2, 1, 3],
  [3, 4, 2],
  [4, 3, 1], [4, 2, 1],
  [5, 2, 4], [5, 4, 2],
]

What’re the subproblems?
For non-negative number i, giving that any path contain at most i edges, what’s the shortest path from starting vertex to other vertices?

How to solve the subproblems?
Start from the basic case which i is 0, in this case, distance to all the vertices except the starting vertex is infinite, and distance to the starting vertex is 0.
For i from 1 to vertices-count — 1(the longest shortest path to any vertex contain at most that many edges, assuming there is no negative weight circle), we loop through all the edges:
For each edge, we calculate the new distance edge[2] + distance-to-vertex-edge[0], if the new distance is smaller than distance-to-vertex-edge[1], we update the distance-to-vertex-edge[1] with the new distance.

How to construct the final result?
If all we want is the distance, we already get it from the process, if we also want to construct the path, we need also save the previous vertex that leads to the shortest path, which is included in DEMO below.

Conclusion

Dynamic programming’s rules themselves are simple; the most difficult parts are reasoning whether a problem can be solved with dynamic programming and what’re the subproblems.
As many other things, practice makes improvements, please find some problems without looking at solutions quickly(which addresses the hardest part — observation for you). Hopefully, it can help you solve problems in your work 😃

Please let me know your suggestions about this article, thanks!