Dynamic programming is both a mathematical optimization method and a computer programming method. By definition, it is a technique in computer programming that helps to efficiently solve a class of problems with overlapping subproblems and optimal substructure properties.
It refers to simplifying a complicated problem by breaking it into simpler subproblems.
All problems can’t be solved using the dynamic programming paradigm. Still, if a problem can be solved optimally by breaking it into subproblems and then recursively finding the optimal solutions, it is said to have an optimal substructure.
Example: Fibonacci sequence
The Fibonacci sequence is a set of integers (the Fibonacci numbers) that starts with a zero, followed by a one, then by another one, and then by a series of steadily increasing numbers.
The solution for the calculation of the Fibonacci number written recursively would be:
function fibonacci(n) {
if (n <= 1) return n
return fibonacci(n − 1) + fibonacci(n − 2)
}
Recursion as a problem solution is usually not the best approach if recursion depth can potentially increase.
Understanding why the recursive Fibonacci method is so slow helps to understand how many “recursive calls” the method makes. In general for n > 3, a call to fibonacci(n) makes 2 recursive calls to fibonacci(n-1) and fibonacci(n-2). These recursive calls, in turn, create more recursive calls.
We need to utilize dynamic programming to escape the abyss of recursion depths.
The approach would be to store already calculated Fibonacci numbers.
function fibonacci(n) {
f = [ ]
f [0] = 0
f [1] = 1
for (i = 2; i <= n; i++) {
f [i] = f [i - 1] + f [i - 2]
}
return f [n]
}
The technique of storing values of subproblems is called memoization. Dynamic programming by memoization is a top-down approach to dynamic programming since we first break the problem into subproblems and then calculate and store values.
In the bottom-up approach, we calculate the smaller values of fibonacci first, then build larger values from them.
function fibonacci(n) {
a = 0
b = 1
if (n == 0)
return a
for (i =2; i <=n; i++) {
c = a + b
a = b
b = c
}
return b
}
Conclusion
The time complexity of the recursive solution is exponential – O(Φn), to be exact. This is due to solving the same subproblems multiple times.
For the top-down approach, we only solve each subproblem one time. Since each subproblem takes a constant amount of time to solve, this gives us an O(N) time complexity. However, since we need to keep an array of size N + 1 to save our intermediate results, the space complexity for this algorithm is also O(N).
In the bottom-up approach, we also solve each subproblem only once. So the time complexity of the algorithm is also O(N). Since we only use two variables to track our intermediate results, our space complexity is constant, O(1).
Challenge
Solve this task and visit us! First three people who send us the correct answer here will get a chance to meet our Talent team, visit Atlantbh office* and get a gift!
We are renovating our office and want to build a few pillars. You will be given lego blocks (each has the same height and width). Each pillar must be higher than previously built pillars, meaning each pillar must contain a unique number of blocks. If given N number of pillars, how many different combinations of pillars with different heights can you build?
Hint 1: If you are given 5 lego blocks, you can build two pillars with different heights, 2 and 3, OR two pillars with heights 1 and 4. So the number of COMBINATIONS is 2.
Hint 2: if you are given 6 lego blocks, you can build two pillars with heights 1 and 5, two pillars with heights 2 and 4, or three pillars with heights 1, 2, and 3. The number of COMBINATIONS is 3.
You need to write a function count_pillars(n) in any programming language, which takes n as the number of lego blocks and retrieves the number of possible combinations of pillars for the given number of blocks.
You need to provide two solutions.
First must be written using recursion.
In the second, use dynamic programming based on the first solution.
The maximum number of lego blocks in test cases will be 300 000.
If you know the solution, send it to us here by the 20th of February in the desired programming language. Don’t forget to explain your logic in solving this task.
*Atlantbh does not cover the cost of transportation to the office.
“Dynamic programming” Tech Bite was brought to you by Zurahid Omeragić, Software Engineer at Atlantbh.
Tech Bites are tips, tricks, snippets or explanations about various programming technologies and paradigms, which can help engineers with their everyday job.
QA Challenges on Data Processing-based Solutions
Leveraging WordPress Custom Post Types
How many digits does count_pillars(300000) return?