Have you ever climbed a mountain, only to realize halfway up that there was a much easier path you could have taken? In the world of problem-solving algorithms, this scenario translates to inefficient solutions that could be dramatically improved. Enter dynamic programming, a powerful technique that ensures you always take the most efficient route.
This article delves into the fascinating world of dynamic programming. We’ll explore its key features, understand the different methods it employs, and illuminate these concepts with real-world illustrations.
What is Dynamic Programming in General?
Definition of dynamic programming:
Dynamic programming is a problem-solving method in computer programming. It breaks down a complex problem into smaller, manageable parts, saves its solutions, and then optimizes those solutions to find the best overall answer. This often involves finding the highest or lowest value for a given query.
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.
Advantages and Disadvantages of DP for Business
The main idea of dynamic programming algorithms in machine learning should be traced in the presented example: we sacrifice a solid amount of memory (O(nm) instead of O(1)), but get just a crazy time gain (O(nm) vs O(3^n)). Let us list all the key features of dynamic programming.
Advantages:
- Speed. Unsolvable issues become solvable, in most cases, in squared time! One operation to fill each table cell and the concern is solved.
- Universality. One Ring to rule them all—creating a compact system of multiple rules for filling the table guarantees the solution of the problem on any data. No exceptions, no boundary cases, a few lines, and the complicated difficulty is solved.
- Accuracy. Since the dynamic programming algorithm considers absolutely all possible options and scenarios, it is guaranteed to find the best solution. No loss of precision, no approximate answers. If there is a solution—it will be found.
Disadvantages:
- Memory. Most dynamic programming algorithms take time to build and fill tables that consume memory resources. This can be an issue if the tables themselves are massive, or if you need to build a lot of such tables and keep them all in memory to solve a problem.
- Cognitive load. Solving a tangled issue with a compact system of rules is a very tempting idea. But there is a nuance here: one must learn to “think in dynamic programming” to compose or at least understand these systems of rules. This is the reason for the rather controversial reputation of dynamic programming.
Best Technologies for Dynamic Programming
Dynamic programming is a technique, not a specific technology, so it doesn’t require specific programming languages or tools. However, certain languages and features can make implementing dynamic programming algorithms easier and more efficient. Here’s a breakdown of some factors to consider:
1.Languages with Built-in Memoization:
Python: Python offers libraries like functools.lru_cache that implement memoization, a key concept in dynamic programming. This allows you to cache the results of subproblems, avoiding redundant calculations and improving efficiency.
JavaScript: While JavaScript doesn’t have built-in memoization, libraries like memoize.js provide similar functionality.
Ruby: Ruby is great for dynamic programming because it has tools that support memoization. This feature lets you store the results of function calls to improve efficiency. For example, the memoize method from the memoizer gem or the cache method from the ActiveSupport library can help speed up dynamic programming algorithms.
2.Languages with Strong Functional Programming Features:
Haskell, Scala: These languages emphasize immutability and pure functions, which align well with the recursive nature of dynamic programming algorithms. This can lead to cleaner and more concise code.
3.General-Purpose Languages:
C++, Java: While not specifically designed for dynamic programming, these languages offer the flexibility to implement dynamic programming solutions effectively. However, you might need to manually implement memoization techniques using data structures like arrays or hash tables.
Rust:
Focus on Performance and Memory Safety: Rust shines in scenarios where performance and memory safety are paramount. Its ownership and borrowing system ensures efficient memory management, making it a strong choice for implementing complex dynamic programming algorithms that might handle large datasets.
Manual Memoization: Rust doesn’t have built-in memoization. However, its powerful functional programming capabilities allow you to implement memoization techniques manually using closures and hash tables. This approach offers fine-grained control over memory usage and can be particularly efficient for problems with specific subproblem dependencies.
Dynamic Typing and Conciseness: Groovy’s dynamic typing allows for more concise code compared to statically typed languages like Rust. This can be advantageous for rapid prototyping and experimentation with dynamic programming algorithms.
Leveraging Java Libraries: Groovy seamlessly integrates with Java libraries. You can leverage existing Java libraries for memoization or dynamic programming functionalities, reducing development time. However, these libraries might introduce some overhead compared to manual implementations in Rust.
4.Focus on Problem-Solving Skills:
Ultimately, the best “technology” for dynamic programming is a solid understanding of the technique itself and strong problem-solving skills. Being able to identify problems that can be solved using dynamic programming and break them down into subproblems is more important than the specific programming language you choose.
Additional Tips:
Consider the size and complexity of your problem. For smaller problems, a simple implementation in any language might suffice. For larger problems, languages with built-in memoization or strong functional programming features can offer performance benefits.
If you’re new to dynamic programming, start by practicing with well-documented implementations in different languages. This can help you grasp the concepts and choose the language that best suits your learning style and project needs.
Remember, the key to dynamic programming is understanding the logic and efficiently solving problems through the decomposition and reuse of subproblems. The right programming language becomes a tool to express that logic effectively.
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.
Do Dynamic Programming Algorithms Solve Real-World Problems?
Yes, of course! Dynamic programming algorithms solve problems in the real world perfectly. It’s not effortless to see, though.
One of the most obvious tasks is building a route that goes through multiple points. Online map apps and cab services often run into this kind of issue (it’s likely that some services use other APIs). For example, you want to take a group of friends for a cab ride after a fun party. Well, how do you know who to send home first and through which streets to go? This is where our dynamic programming works with graph theory. From classical DP issues, this intersects with the problem of the traveling salesman.
Accordingly, a similar example in computer networks is when a packet of data needs to be delivered to several recipients at once. The algorithm needs to figure out which route and in what order to deliver the data to all destinations.
The diff utility is also a prime example of the use of dynamic programming. Since the goal is to find similar substrings in two strings, we can clearly see one of the classic dynamic programming issues: finding the largest common subsequence.
Another interesting java algorithm example. Here‘s a story about how a related problem with diff has to be solved in a real application. On the front! These guys are compressing images using dynamic programming. You all know that when compressing an illustration, they use approaches where similar places/pixels are written through less information. But the example above describes an approach of how you can compress an image with a modification of the image content and still retain a high level of information content. That is, if the meaning of the photo was “a dog with a cat on the lawn”, then after cutting it will be the same. And this is not an easy task!
Involved programmers should first separate the business logic from the algorithmic part when using this approach. So that they do not have to explain to people why they missed the bug where they took an element with index 100 (arr[100]) from an array of size 100. But this, of course, does not only apply to dynamic programming algorithms.
Yes, in the world of real outsourcing/outstaffing tasks, you don’t often have to solve problems using dynamic programming. And you don’t have to try to figure out where to apply it. It’s just enough that you already know about this approach, understand how it works, and know where it can be used in real life.
Applications of Dynamic Programming to Algorithmic Problems
To get a better understanding of dynamic programming, we will give an example of solving three different problems. Their complexity increases (the first one is the easiest, the last one is the most difficult).
Task 1: Climbing the ladder
You are climbing a ladder. To get to the top, you have to climb N steps. You can climb one or two stairs per step.
Let us use our algorithm. So, let us have the function dynamic programming_steps(N) – it returns the number of different ways to climb, depending on N steps.
Next, see how the solution to the difficulty behaves depending on the different number of steps.
- DP_steps(1) = 1. Since there is only one way to go up one step – to traverse one step in one step.
- DP_steps(2) = 2. That is, there are two ways to go up two steps. The first way is to take two steps in one step. The second way is to take one step in two steps.
Task 2. Find the size of the longest strictly increasing subsequence
A subsequence is one more sequence in a dynamic programming algorithm that can be obtained from the original one by removing some or no (!) elements from the original sequence.
For example, [2, 4, 1] is a subsequence of [1, 2, 5, 7, 4, 2, 1]. For a sequence to be strictly increasing, each of its elements must be strictly greater than the previous one.
The first thing you can think of is to go through all possible sequences. That is, iterate through all its numbers and every time we come across a number that breaks an ascending sequence, call the method of searching for the longest subsequence starting from that number again.
For example, if we have an array [3, 4, 1, 7] in dynamic programming. And we iterate over it:
- The first element is 3, all good.
- The second element is 4, the sequence is increasing, and everything is good. The length is 2.
- The third element is 1. Yep, the increasing subsequence is broken, we can’t add 1 to it.
Then we start a new search for a strictly increasing sequence, but starting with 1. That is, we call our method for the array [1, 7]. And so on.
In the end, we simply return the size of the largest strictly increasing subsequence. Clearly, if the array is strictly decreasing (for example, [7, 6, 5, 4, 3, 2, 1]), our function will be called recursively many times.
Task 3. About finding the N ugly number
Solution dynamic programming algorithm: go through all numbers in a row, starting with one. At the same time, count the number of ugly numbers encountered. When we get to the right number, we return it.
The above algorithm has the function is_number_ugly. This is a simple function that checks for prime divisors of a number. If the prime divisors are only 2, 3 and 5, this function returns true, and otherwise, it returns false.
The main drawback of this algorithm is that for every number we need to check whether it is ugly or not. And this task is not done in a constant amount of time, so we want to somehow avoid such calculations.
Dynamic Programming in Action: Real-World Use Cases
Dynamic programming isn’t just theoretical; it’s a powerful tool used across various disciplines! Here are some real-world applications that showcase its versatility:
1.Computer Science:
Shortest Path Algorithms: Imagine a maze. Dynamic programming can be used to find the shortest path from the entrance to the exit. It breaks down the maze into smaller sub-problems, calculating the optimal route for each section and efficiently piecing them together to form the overall shortest path. This is used in applications like GPS navigation systems.
Text Editing and Spell Checkers: How do spell checkers suggest corrections so accurately? Dynamic programming allows them to analyze the entire word and identify the most likely correct spelling based on previously encountered words and known patterns.
Sequence Alignment in Bioinformatics: Scientists use dynamic programming to compare DNA or protein sequences and identify similarities or mutations. This helps in analyzing genetic diseases, understanding evolutionary relationships between species, and developing targeted drugs.
2.Finance and Economics:
Portfolio Optimization: Investment firms leverage dynamic programming to create optimal investment portfolios. It considers factors like risk tolerance, market trends, and expected returns to build a portfolio that maximizes profit while minimizing risk.
Dynamic Pricing: Have you ever noticed airline ticket prices fluctuate wildly? Dynamic programming helps airlines optimize their pricing strategies in real-time based on demand, competitor pricing, and historical data, maximizing revenue while maintaining competitiveness.
3.Artificial Intelligence:
Speech Recognition: Speech recognition software, like Siri or Alexa, utilizes dynamic programming to understand spoken language. It breaks down complex sentences into smaller parts like phonemes and analyzes the combinations most likely to represent the spoken word.
Machine Translation: Translation software employs dynamic programming to translate languages accurately. It considers the grammatical structure of both languages and finds the most optimal sequence of words in the target language to convey the source language’s meaning.
These are just a few examples, and the applications of dynamic programming continue to expand. As computing power increases and algorithms evolve, we can expect even more innovative applications of this powerful technique in the future.
Wrapping Up
Let’s sum up the information from our new article, dynamic programming is an approach to solving algorithmic problems that can greatly reduce the running time of programs. It potentially uses a non-constant amount of memory (that is, the larger the difficulty is—the more memory is needed to solve it). But memory costs are often negligible compared to the acceleration we get.
Dynamic programming algorithms are rarely used in the day-to-day tasks of software development engineers and is not a trivial/native approach. But understanding that such a method exists and that it can be used to improve program performance significantly is good both for solving specific problems and for a specialist’s worldview.