Question 1

What is Dynamic Programming in General?

Accepted Answer

Dynamic programming is a special approach to problem-solving. Unfortunately, there is no single definition of dynamic programming, but let's try to form one by ourselves. The idea is that the optimal solution can often be found by considering all possible ways of solving an issue and choosing among them the best one.

The operation of dynamic programming is very similar to recursion with memoization of intermediate solutions, which is also called memoization. Recursive algorithms tend to divide a large concern into smaller subtasks and solve them. Dynamic algorithms divide the difficulty into chunks and compute them one at a time, building up solutions step by step. Therefore, dynamic algorithms can be thought of as recursion, working from the bottom up.

It's about Richard Bellman, who invented and established the concept of “dynamic programming” in the scientific community. In 1940, he used the term for issues where the solution to one part of the problem depended on another. Then in 1953, Bellman modified and expanded the definition of dynamic programming to its current form. 

He describes the naming situation of this concept in an amusing way. Bellman had to come up with a name, but the official representative to whom he reported at the time strongly hated (the mathematician emphasizes that he “hated”) the terms and did not want to deal with them. Every time, all the employees had to literally tremble with fear because their boss couldn't understand something and stirred it with mud in his unfunny puns. And especially the math terms! 

According to the book “Dynamic Programming”, Richard Bellman spent a lot of time and effort coming up with a name. The word “programming” was chosen as an analog to the word “planning”, which did not fit for a number of different reasons (the Soviets had planned something all the time).

And the word “dynamic” was decided based on the fact that, in addition to conveying the essence of the approach, it was hard to come up with something derogatory, or preparatory with it. Bellman didn't want an executive to somehow obfuscate his term. Not even an official could have done it so easily (readers, of course, will find a couple of variations). This is how the term “dynamic programming” was formed.

Summing up, dynamic programming is an approach to solving problems, where the original problem is broken down into smaller subtasks that are easier to solve. And then smaller solutions of these subtasks can be used to fix the original error. Nevertheless, the approach has some essential features:

It makes sense if the solutions of subtasks can be used effectively (to memorize, for example);
subtasks have a common structure, so some homogeneous methods can be applied to their solution, instead of solving each separately with different algorithms.

Question 2

How to Apply Dynamic Programming Algorithms to Solve Problems

Accepted Answer

The demonstration subject will be a classical dynamic programming concern—Levenshtein Distance. Despite the seemingly complex name, in fact, its difficulty is in the transformation of one word into another by adding, deleting and replacing letters with a minimum number of operations.

This concern of dynamic programming can be formulated as follows: find the minimum “distance” between two words. The distance in this case will be the minimum number of operations to be applied to the first word to get the second (or vice versa).

We have three available operations:

insert – add one letter anywhere in the word, including its beginning and ending
delete – remove one letter from any place in the word
replace – replace one letter in a certain place with another

All these operations have an equal cost: +1 to the distance between words.

Take, for example, two simple words, MONEY and MONKEY. What is the minimum number of operations needed to turn MONEY into MONKEY? The shrewd human eye quickly guesses one: add a K between the third and the fourth letter.

Let's take a more complicated case. Try turning SUNDAY into SATURDAY, and we see that the number of combinations of dynamic programming to search is potentially gigantic. If we solve the problem by brute force, we can consider all possible combinations, like in the password-cracking example. Instead of a possible 94 candidate characters, we have three operations – insert, delete, and replace. Three combinations for the first letter, 3×3 for two letters, 3×3×3 for three letters, and 3^N for N letters.

Memoization and tabulation

Dynamic programming memoization is an optimization technique that allows you to memorize the results and all algorithms of calculations and reuse them when you need to repeat this calculation. A favorite example: when calculating the seventh Fibonacci number, you can memorize the fourth Fibonacci number and not calculate it every time, but only once. This technique is also described as top-down.

Tabulation is an optimization technique that starts by solving subtasks with the simplest one and then, as you progress, deals with more and more complex subtasks until the main problem is solved. In doing so, solutions to simpler subtasks are used to solve more complex subtasks.  In contrast to memoization, this approach is called “bottom-up” because you first take on the simplest tasks.

Eugene Syuyva

What is Dynamic Programming? Features, Methods, and Real-World Uses

What Is Blockchain, and How Does It Work?

Quality Assurance vs Quality Control: 4 Major Differences You Need to Know

What’s New in AI and ML? 10 Technologies that Are Evolving Right Now

Top 10 Agile Methodologies and Frameworks for Robust App Development

6 Cost-Saving Techniques To Improve the Software Development Process

Unforeseen Boundaries: Exploring Legal Issues and Challenges in Smart Contracts

8 Great Examples of the Most Popular Smart Contract Platforms

How to Skyrocket Your Business with the Power of Smart Contracts

Scale Your Business With LITSLINK!

Thank you!