Dynamic Programming is one of the important topics from DSA. It is asked in most of the interviews. Having a good grasp of Dynamic Programming helps you crack most interview questions. Let’s discuss different patterns of dynamic programming.
What is Dynamic Programming?
Dynamic Programming is used to optimize our code and reduce our time complexity by storing the repeated value. If we need the same value later, we do not have to recalculate it; instead, we can use the already computed value.
There are two different types of DP, Top-Down (Recursive) and Bottom-Up (tabulation).
6 Different Patterns Of Dynamic Programming
There are some basic patterns of Dynamic Programming. If you understand them all, all the questions of Dynamic Programming become a piece of cake for you. As all of them have the same approach, You just need to find which approach works on that question. Let’s see all the approaches one by one along with their code.
1) Unbounded Knapsack Pattern
In this type of question, you are generally given a target element, and you have to form that target by taking some elements from the array. You have to perform any of the mathematical computations based on the question. For example, find the target by taking the subset-sum of the given array. You have to take care that repetition is not allowed. This means if you had used some element from the array you cannot use it again.
Let’s see the basic template for this problem.
C++ Code
int function(vector<int>& arr, vector<int>& value, int target){
// arr is array
// value is values associated with each element in the array
int sz = arr.size();
vector<vector<int>>dp(sz+2, vector<int>(target+2,0));
for(int i=1; i<=sz; i++){
for(int j=1; j<=target; j++){
if( j < arr[i-1]){
dp[i][j] = dp[i-1][j];
}
else{
dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i-1][j-arr[i-1]]);
}
}
}
return dp[sz][target];
}Java Code
public static int function(int[] arr, int[] value, int target) {
int sz = arr.length;
int[][] dp = new int[sz + 2][target + 2];
for (int i = 1; i <= sz; i++) {
for (int j = 1; j <= target; j++) {
if (j < arr[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - arr[i - 1]]);
}
}
}
return dp[sz][target];
}Python Code
def function(arr, value, target): sz = len(arr) dp = [[0] * (target + 2) for _ in range(sz + 2)] for i in range(1, sz + 1): for j in range(1, target + 1): if j < arr[i - 1]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - arr[i - 1]]) return dp[sz][target]
2) Bounded Knapsack
This pattern is similar to the above knapsack pattern, the only difference is that we can use the same element of the array multiple times. Some questions based on this pattern are “Coin Change,” “Coin Change II,” etc.
Let’s understand the code for the above pattern.
C++ Code
int function(vector<int>& arr, vector<int>& value, int target){
// arr is array
// value is values associated with each element in the array
int sz = arr.size();
vector<vector<int>>dp(sz+2, vector<int>(target+2,0));
for(int i=1; i<=sz; i++){
for(int j=1; j<=target; j++){
if( j < arr[i-1]){
dp[i][j] = dp[i-1][j];
}
else{
// the only difference between the bounded and unbounded is here dp[i] is
// used unlike unbounded where we are using dp[i-1].
dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i][j-arr[i-1]]);
}
}
}
return dp[sz][target];
}Java Code
public static int function(int[] arr, int[] value, int target) {
int sz = arr.length;
int[][] dp = new int[sz + 2][target + 2];
for (int i = 1; i <= sz; i++) {
for (int j = 1; j <= target; j++) {
if (j < arr[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i][j - arr[i - 1]]);
}
}
}
return dp[sz][target];
}Python Code
def function(arr, value, target): sz = len(arr) dp = [[0] * (target + 2) for _ in range(sz + 2)] for i in range(1, sz + 1): for j in range(1, target + 1): if j < arr[i - 1]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], value[i - 1] + dp[i][j - arr[i - 1]]) return dp[sz][target]
3) Longest Increasing Subsequence
This pattern was followed in most of the DP questions. In this type of question, you have to find the longest increasing subsequence. The subsequence is a sub-part that is created by deleting some elements from the array.
In this pattern, we will check if the previously computed subsequence’s last element is smaller than the current element or not. If it is, we will check dp[j]+1> dp[i]. If it is, then we will update dp[i] = dp[j] + 1.
Let’s understand the code for the above pattern.
C++ Code
int LIS(vector<int>& arr){
int mx = 0;
vector<int>dp(arr.size()+2,1);
for(int i=0;i<=arr.size(); i++){
for(int j=0;j<i;j++){
if((arr[i]>arr[j]) && (dp[j]+1 > dp[i])){
dp[i] = dp[j] + 1;
}
}
mx = max(mx, dp[i]);
}
return mx;
}Java Code
public static int LIS(int[] arr) {
int mx = 0;
int[] dp = new int[arr.length + 2];
Arrays.fill(dp, 1);
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
mx = Math.max(mx, dp[i]);
}
return mx;
}Python Code
def LIS(arr): mx = 0 dp = [1] * (len(arr) + 2) for i in range(len(arr)): for j in range(i): if arr[i] > arr[j] and dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 mx = max(mx, dp[i]) return mx
4) Longest Common Subsequence
In this type of question, you are given two strings, let’s say s1 and s2. You have to determine whether s2 completely lies in s1 or not. There may be some changes like written total number of different ways in which s2 can be formed from s1. Palindrome questions are also based on this pattern. You can try some questions like “Longest Palindromic Substring,” “Delete Operation For Two Strings,” etc.
Let’s examine the code for the above pattern.
C++ Code
int LCS(string s1, string s2)
{
vector<vector<int>> dp(s1.size()+2,vector<int>(s2.size()+2,0));
for(int i=1;i<=s1.size();i++)
{
for(int j=1;j<=s2.size();j++)
{
if(s1[i-1]==s2[j-1]){
dp[i][j] = 1+dp[i-1][j-1];
}
else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
int sz1 = s1.size();
int sz2 = s2.size();
return dp[sz1][sz2];
}Java Code
public static int LCS(String s1, String s2) {
int[][] dp = new int[s1.length() + 2][s2.length() + 2];
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int sz1 = s1.length();
int sz2 = s2.length();
return dp[sz1][sz2];
}Python Code
def LCS(s1, s2): dp = [[0] * (len(s2) + 2) for _ in range(len(s1) + 2)] for i in range(1, len(s1) + 1): for j in range(1, len(s2) + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1] else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) sz1 = len(s1) sz2 = len(s2) return dp[sz1][sz2] s1 = "abcde" s2 = "ace" print(LCS(s1, s2))
5) Kadane’s Algorithms Pattern
This is the easiest pattern. Kadane’s algorithm asked directly in the interviews like Amazon. This helps us to find the maximum subarray sum in O(n) time complexity.
Let’s examine the code for the above pattern.
C++ Code
int Kadane(vector<int>& arr){
int mx = INT_MIN;
int current = 0;
for(int i=0; i<arr.size(); i++){
if(current >= 0){
current+= arr[i];
}else{
current = arr[i];
}
mx = max(mx, current);
}
return mx;
}Java Code
public static int Kadane(int[] arr) {
int mx = Integer.MIN_VALUE;
int current = 0;
for (int i = 0; i < arr.length; i++) {
if (current >= 0) {
current += arr[i];
} else {
current = arr[i];
}
mx = Math.max(mx, current);
}
return mx;
}Python Code
def Kadane(arr):
mx = float('-inf')
current = 0
for i in range(len(arr)):
if current >= 0:
current += arr[i]
else:
current = arr[i]
mx = max(mx, current)
return mx6) Catalan
In this type of question, we are generally asked to count something like nodes, brackets, etc. For example, in questions like “Unique Binary Search Trees,” we asked to find the total number of unique BSTs.
Let’s understand the code for the above pattern.
C++ Code
int catalan(int n)
{
vector<int>dp(n+1, 0);
dp[0]=1;
dp[1]=1;
for(int i = 2; i < n+1; i++)
{
dp[i]=0;
for(int j = 0; j < i; j++)
{
dp[i] = dp[i] + (dp[j] * dp[i-1-j]);
}
}
return dp[n];
}Java Code
public static int catalan(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < n + 1; i++) {
dp[i] = 0;
for (int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp[n];
}Python Code
def catalan(n): dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 for i in range(2, n + 1): dp[i] = 0 for j in range(i): dp[i] += dp[j] * dp[i - 1 - j] return dp[n] n = 5 print(catalan(n))
Conclusion
We have seen various patterns of Dynamic Programming. These patterns help you to solve most of the Dynamic Programming questions.
