Dynamic programming is a useful problem-solving technique that every developer should know. While the basics are easy to learn, dynamic programming can be difficult to master. In this post, we break down the fundamentals of dynamic programming and share challenge questions to start practicing.
What is Dynamic Programming?
Dynamic programming is a problem-solving paradigm used to find a solution by breaking the larger problem into subproblems. This approach takes advantage of the fact that the optimal solution to a problem depends upon the optimal solution to its subproblems.
But dynamic programming isn’t the right approach for every problem. You can use dynamic programming to solve a problem if that problem has two characteristics:
- Overlapping Subproblems: The problem can be divided into a number of subproblems of similar type but of smaller size than the original one.
- Optimal Substructure Property: The optimal solution to the problem can be formulated from the optimal solution to its subproblems.
Dynamic Programming vs Greedy Algorithms
One helpful way to understand dynamic programming is to compare it to greedy algorithms.
A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step to find the global or overall optimal solution to the entire problem.
However, a greedy algorithm isn’t always the right approach, as it can create an inaccurate or suboptimal solution. In some situations, the largest sum or most optimal path is “hiding behind the door” of an answer that at first appears small or suboptimal.
In contrast, dynamic programming can break those decisions into components and solve for the overall optimal solution. The drawback, however, is that dynamic programming can be challenging, compared to the easier greedy algorithms.
Dynamic Programming Methods
Dynamic Programming has two methods that can be used to solve problems: top-down and bottom-up.
Top-Down Approach
A top-down (recursive) approach tries to solve the bigger problem by recursively finding the solution to smaller problems while also storing local solutions in a look-up table such that those are not computed each time. This technique is called Memo-ization.
Memoization
The advantage of the top-down approach is that it’s more intuitive to come up with solutions than the other method. However, this doesn’t always produce the most optimal solution, as it often leads to code that is slower and lengthier.
Example
Problem
F(n) = (F(n – 1) + F(n -3), if (n >=3)
F(n) = 7, otherwise
Given n, find the nth term of the recurrence.
Top-Down Solution
int F[MAXSIZE] ;
// set F to some unique value like -1 in this case.
int solve(int n){
if(n < 3){
return 7 ; // recurrence definition
}
int &ret = F[n] ; // cache technique
if(ret != -1) // absence of -1 indicate that this is already computed
return ret ; // use this computed result
ret = solve(n-3) + solve(n-1) ; // compute otherwise
return F[n] = ret ; // final return computed answer
}
Bottom-Up Approach
The bottom-up (iterative) approach is the opposite of the top-down approach in that you start from the smallest solution and go up to the required solution. The bottom-up approach tends to produce shorter, more optimal code. However, thinking of a bottom-up solution is less intuitive, and their base cases are often trickier than top-down base cases.
Example
Problem
F(n) = (F(n – 1) + F(n -3), if (n >=3)
F(n) = 7, otherwise
Given n, find the nth term of the recurrence.
Bottom-Up Solution
int F[MAXSIZE] ;
int solve(int n){
F[0] = F[1] = F[2] = 7 ; // recurrence definition
for(int i=3;i<=n;i++)
F[i] = F[i-1] + F[i-3] ; // recurrence definition
return F[n] ;
}
Dynamic Programming Questions
Problem: Row of Numbers
You have a row of numbers. In every turn, you can remove either the leftmost or the rightmost number and get points equal to turn_number x value of removed number. What is the maximum number of points you can get?
Solution
While you might think to use a greedy algorithm, that solution is not correct. [2, 3, 5, 1, 4] is a counter-example. This leads to the answer 2 x 1 + 3 x 2 + 4 x 3 + 1 x 4 + 5 x 5 = 49. The optimal answer in this case would be 2 x 1 + 4 x 2 + 1 x 3 + 3 x 4 + 5 x 5 = 50.
The correct solution is a dynamic programming approach.
Assume we have a function f(i, j) which gives us the optimal score of picking numbers with indices from i to j assuming the picking begins at turn number 1. Then, our answer would be f(1, n) where n is the total count of numbers.
However, notice that since we can only pick the leftmost one or the rightmost one, f(1, n) = max(g(2, n)) + val1, g(1, n – 1) + valj) where g(i, j) is the optimal cost assuming picking begins at turn number 2.
A small observation: g(i, j) = f(i, j) + sum of all numbers from i to j.
Which means: f(i, j) = max(f(i, j – 1)) + sum(i, j – 1) + valj, f(i + 1, j) + sum(i + 1, j)
Computing this relation by recursion will take an exponential amount of time because the problem of size j – i gets reduced to two instances of problem sizes j – i -1 each.
This gives the recurrence:
T(n) = 2T(n – 1)
or, T(n) = O(2n)
Let’s try to handle this.
First of all, notice that this problem has both the required properties of a dynamic programming problem. The answer depends on the answers to smaller subproblems.
These subproblems overlap with each other: f(i, j – 1) and f(i + 1, j) both call f(i + 1, j – 1).
However, there are only O(n2) different parameters of f and, therefore, only O(n2) different values of f.
So, we can use memoization while calculating f. Once it has been evaluated, all subsequent calls to this state are answered using the stored value.
The complexity of this solutions is: number of states x number of transitions from each state, which is O(n2) for this problem.
It is important to note that every recursion must have a base case in order to terminate. The base case here is pretty simple: f(i, i) = vali: ∀i
Problem: Max Array Sum
Difficulty Level: Medium
Given an array of integers, find the subset of non-adjacent elements with the maximum sum. Calculate the sum of that subset. It is possible that the maximum sum is 0, the case when all elements are negative.
Example
The following subsets with more than 1 element exist. These exclude the empty subset and single element subsets which are also valid.
Subset Sum
[-2, 3, 5] 6
[-2, 3] 1
[-2, -4] -6
[-2, 5] 3
[1, -4] -3
[1, 5] 6
[3, 5] 8
The maximum subset sum is 8. Note that any individual element is a subset as well.
arr = [-2, -3, -1]
In this case, it is best to choose no element:
return 0.
Function Description
Complete the maxSubsetSum function in the editor below.
maxSubsetSum has the following parameter(s):
- int arr[n]: an array of integers
Returns
– int: the maximum subset sum
Input Format
The first line contains an integer, n.
The second line contains n space-separated integers arr[i].
Constraints
- 1 <= n <= 105
- -104 <= arr[i] <= 104
Sample Input
5
2 1 5 8 4
Sample Output
11
Explanation
Our subsets are [2, 5, 4]. [2, 5], [2,8], [2, 4], [1, 8], [1, 4] and [5, 4] The maximum subset sum is 11 from the first subset listed.
Hint
To solve the problem with dynamic programming, work through the array, keeping track of the max at each position until you get to the last value of the array. You should start with the base cases defined before iterating through the remainder of the array.
Challenge Problem: Billboards
Difficulty Level: Advanced
Below is an advanced-level dynamic programming problem that covers topics such as dynamic programming and priority queue. Only 36.09% of developers in the HackerRank Community that have attempted this problem have succeeded. Good luck!
Question
ADZEN is a popular advertising firm in your city that owns all n billboard locations on Main Street. The city council passed a new zoning ordinance mandating that no more than k consecutive billboards may be up at any given time. For example, if there are n = 3 billboards on Main street and k = 1, ADZEN must remove either the middle billboard, the first two billboards, the last two billboards, or the first and last billboard.
Being a for-profit company, ADZEN wants to lose as little advertising revenue as possible when removing the billboards. They want to comply with the new ordinance in such a way that the remaining billboards maximize their total revenues (i.e., the sum of revenues generated by the billboards left standing on Main street).
Given n, k, and the revenue of each of the n billboards, find and print the maximum profit that ADZEN can earn while complying with the zoning ordinance. Assume that Main street is a straight, contiguous block of n billboards that can be removed but cannot be reordered in any way.
For example, if there are n = 7 billboards, and k = 3 is the maximum number of consecutive billboards that can be active, with revenues = [5, 6, 4, 2, 10, 8, 4], then the maximum revenue that can be generated is 37: 5 + 6 + 4 + 2 + 10 + 8 + 4.
Function Description
Complete the billboards function in the editor below. It should return an integer that represents the maximum revenue that can be generated under the rules.
billboards has the following parameter(s):
- k: an integer that represents the longest contiguous group of billboards allowed
- revenue: an integer array where each element represents the revenue potential for a billboard at that index
Input Format
The first line contains two space-separated integers, n (the number of billboards) and k (the maximum number of billboards that can stand together on any part of the road).
Each line i of the n subsequent lines contains an integer denoting the revenue value of billboard i (where 0 <= i <= n).
Constraints
- 1 <= n < 10^5
- 1 <= k <=n
- 0 <= revenue value of any billboard <= 2 * 10^9
Output Format
Print a single integer denoting the maximum profit ADZEN can earn from Main street after complying with the city’s ordinance.
Sample Input 0
6 2
1
2
3
1
6
10
Sample Output 0
21
Explanation 0
There are n = 6 billboards, and we must remove some of them so that no more than k = 2 billboards are immediately next to one another.
We remove the first and fourth billboards, which gives us the configuration _ 2 3 _ 6 10 and a profit of 2 + 3 + 6 + 10 + 21. As no other configuration has a profit greater than 21, we print 21 as our answer.
Sample Input 1
5 4
1
2
3
4
5
Sample Output 1
14
Explanation 1
There are n = 5 billboards, and we must remove some of them so that no more than k = 4 billboards are immediately next to one another.
We remove the first billboard, which gives us the configuration _ 2 3 4 5 and a profit of 2 + 3 +4 + 5 = 14. As no other configuration has a profit greater than 14, we print 14 as our answer.
Resources
Dynamic Programming Interview Questions