What is Dynamic Programming in General?

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.

How to Apply Dynamic Programming Algorithms to Solve Problems

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.

LITSLINK Blog

AI Map

A free interactive map of AI showcasing 50+ countries and their top AI products in 2026

Check AI Map now!

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

22 January, 2025 by Eugene Syuyva in Development

Solving a jigsaw puzzle without a picture of the final solution is going to take you an eternity, isn’t it? Imagine doing the same with the pieces, knowing exactly which ones fit where. That is...

How to Easily Integrate Generative AI into Workflow for Best Results

13 November, 2024 by Viacheslav Petrenko in Artificial Intelligence

Imagine automating tasks that once required hours of manual labor or generating creative ideas at the click of a button. That’s precisely what many businesses are discovering with generative AI...

Unlocking Competitive Edge: Harnessing the Potential of Machine Learning Across Various Industries [Includes Infographic]

01 November, 2024 by Anastasia Rashevskaya in Artificial Intelligence Data Science

The tide is turning. ML in business is no longer a futuristic fantasy; it’s a powerful reality reshaping industries at an unprecedented pace. From streamlining factory operations to...