{"id":2522,"date":"2024-03-18T07:45:05","date_gmt":"2024-03-18T07:45:05","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2522"},"modified":"2025-04-08T11:29:55","modified_gmt":"2025-04-08T11:29:55","slug":"different-patterns-of-dynamic-programming","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/different-patterns-of-dynamic-programming\/","title":{"rendered":"6 Different Patterns Of Dynamic Programming (with code)"},"content":{"rendered":"\n

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. <\/p>\n\n\n\n

What is Dynamic Programming?<\/strong><\/h2>\n\n\n\n

Dynamic Programming<\/a> 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. <\/p>\n\n\n\n

There are two different types of DP, Top-Down (Recursive) and Bottom-Up (tabulation).<\/p>\n\n\n\n

6 Different Patterns Of Dynamic Programming<\/strong><\/h2>\n\n\n\n

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\u2019s see all the approaches one by one along with their code.<\/p>\n\n\n\n

1) Unbounded Knapsack Pattern<\/strong><\/h3>\n\n\n\n

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.<\/p>\n\n\n\n

Let\u2019s see the basic template for this problem.<\/p>\n\n\n\n

C++ Code<\/strong><\/h4>\n\n\n\n
int function(vector<int>& arr, vector<int>& value, int target){\n\n\u00a0\u00a0\u00a0\u00a0\/\/ arr is array\n\n\u00a0\u00a0\u00a0\u00a0\/\/ value is values associated with each element in the array\n\n\u00a0\u00a0\u00a0\u00a0int sz = arr.size();\n\n\u00a0\u00a0\u00a0\u00a0vector<vector<int>>dp(sz+2, vector<int>(target+2,0));\n\n\u00a0\u00a0\u00a0\u00a0for(int i=1; i<=sz; i++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for(int j=1; j<=target; j++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if( j < arr[i-1]){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = dp[i-1][j];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i-1][j-arr[i-1]]);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0return dp[sz][target];\n\n}<\/pre><\/div>\n\n\n\n
Java Code<\/strong><\/h4>\n\n\n\n
public static int function(int[] arr, int[] value, int target) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int sz = arr.length;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int[][] dp = new int[sz + 2][target + 2];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int i = 1; i <= sz; i++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int j = 1; j <= target; j++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (j < arr[i - 1]) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = dp[i - 1][j];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0} else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - arr[i - 1]]);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return dp[sz][target];\n\n\u00a0\u00a0\u00a0\u00a0}<\/pre><\/div>\n\n\n\n
Python Code<\/strong><\/h4>\n\n\n\n
def function(arr, value, target):\n\n\u00a0\u00a0\u00a0\u00a0sz = len(arr)\n\n\u00a0\u00a0\u00a0\u00a0dp = [[0] * (target + 2) for _ in range(sz + 2)]\n\n\u00a0\u00a0\u00a0\u00a0for i in range(1, sz + 1):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for j in range(1, target + 1):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if j < arr[i - 1]:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = dp[i - 1][j]\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - arr[i - 1]])\n\n\u00a0\u00a0\u00a0\u00a0return dp[sz][target]<\/pre><\/div>\n\n\n\n
2) Bounded Knapsack\u00a0<\/strong><\/h3>\n\n\n\n
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 \u201cCoin Change,\u201d \u201cCoin Change II,\u201d etc.<\/p>\n\n\n\n
Let\u2019s understand the code for the above pattern.<\/p>\n\n\n\n
C++ Code<\/strong><\/h4>\n\n\n\n
int function(vector<int>& arr, vector<int>& value, int target){\n\n\u00a0\u00a0\u00a0\u00a0\/\/ arr is array\n\n\u00a0\u00a0\u00a0\u00a0\/\/ value is values associated with each element in the array\n\n\u00a0\u00a0\u00a0\u00a0int sz = arr.size();\n\n\u00a0\u00a0\u00a0\u00a0vector<vector<int>>dp(sz+2, vector<int>(target+2,0));\n\n\u00a0\u00a0\u00a0\u00a0for(int i=1; i<=sz; i++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for(int j=1; j<=target; j++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if( j < arr[i-1]){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = dp[i-1][j];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else{\n\n\u00a0 \u00a0 \/\/ the only difference between the bounded and unbounded is here dp[i] is\n\n\u00a0\u00a0\u00a0\u00a0\/\/ used unlike unbounded where we are using dp[i-1].\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i][j-arr[i-1]]);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0return dp[sz][target];\n\n}<\/pre><\/div>\n\n\n\n
Java Code<\/strong><\/h4>\n\n\n\n
public static int function(int[] arr, int[] value, int target) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int sz = arr.length;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int[][] dp = new int[sz + 2][target + 2];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int i = 1; i <= sz; i++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int j = 1; j <= target; j++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (j < arr[i - 1]) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = dp[i - 1][j];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0} else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i][j - arr[i - 1]]);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return dp[sz][target];\n\n\u00a0\u00a0\u00a0\u00a0}<\/pre><\/div>\n\n\n\n
<\/strong>Python Code<\/strong><\/h4>\n\n\n\n
def function(arr, value, target):\n\n\u00a0\u00a0\u00a0\u00a0sz = len(arr)\n\n\u00a0\u00a0\u00a0\u00a0dp = [[0] * (target + 2) for _ in range(sz + 2)]\n\n\u00a0\u00a0\u00a0\u00a0for i in range(1, sz + 1):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for j in range(1, target + 1):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if j < arr[i - 1]:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = dp[i - 1][j]\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = max(dp[i - 1][j], value[i - 1] + dp[i][j - arr[i - 1]])\n\n\u00a0\u00a0\u00a0\u00a0return dp[sz][target]<\/pre><\/div>\n\n\n\n
3) Longest Increasing Subsequence<\/strong><\/h3>\n\n\n\n
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. <\/p>\n\n\n\n
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.<\/p>\n\n\n\n
Let\u2019s understand the code for the above pattern.<\/p>\n\n\n\n
C++ Code<\/strong><\/h4>\n\n\n\n
int LIS(vector<int>& arr){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int mx = 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0vector<int>dp(arr.size()+2,1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for(int i=0;i<=arr.size(); i++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for(int j=0;j<i;j++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if((arr[i]>arr[j]) && (dp[j]+1 > dp[i])){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i] = dp[j] + 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0mx = max(mx, dp[i]);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return mx;\n\n\u00a0\u00a0\u00a0\u00a0}<\/pre><\/div>\n\n\n\n
<\/strong>Java Code<\/strong><\/h4>\n\n\n\n
public static int LIS(int[] arr) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int mx = 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int[] dp = new int[arr.length + 2];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Arrays.fill(dp, 1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int i = 0; i < arr.length; i++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int j = 0; j < i; j++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i] = dp[j] + 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0mx = Math.max(mx, dp[i]);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return mx;\n\n\u00a0\u00a0\u00a0\u00a0}<\/pre><\/div>\n\n\n\n
Python Code<\/strong><\/h4>\n\n\n\n
def LIS(arr):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0mx = 0\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp = [1] * (len(arr) + 2)\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for i in range(len(arr)):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for j in range(i):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if arr[i] > arr[j] and dp[j] + 1 > dp[i]:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i] = dp[j] + 1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0mx = max(mx, dp[i])\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return mx<\/pre><\/div>\n\n\n\n
4) Longest Common Subsequence<\/strong><\/h3>\n\n\n\n
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 \u201cLongest Palindromic Substring<\/a>,\u201d \u201cDelete Operation For Two Strings<\/a>,\u201d etc.<\/p>\n\n\n\n
Let\u2019s examine the code for the above pattern.<\/p>\n\n\n\n
C++ Code<\/strong><\/h4>\n\n\n\n
int LCS(string s1, string s2)\u00a0\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0vector<vector<int>> dp(s1.size()+2,vector<int>(s2.size()+2,0));\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for(int i=1;i<=s1.size();i++)\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for(int j=1;j<=s2.size();j++)\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(s1[i-1]==s2[j-1]){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = 1+dp[i-1][j-1];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = max(dp[i-1][j], dp[i][j-1]);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int sz1 = s1.size();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int sz2 = s2.size();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return dp[sz1][sz2];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}<\/pre><\/div>\n\n\n\n
Java Code<\/strong><\/h4>\n\n\n\n
public static int LCS(String s1, String s2) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int[][] dp = new int[s1.length() + 2][s2.length() + 2];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int i = 1; i <= s1.length(); i++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int j = 1; j <= s2.length(); j++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (s1.charAt(i - 1) == s2.charAt(j - 1)) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = 1 + dp[i - 1][j - 1];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0} else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int sz1 = s1.length();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int sz2 = s2.length();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return dp[sz1][sz2];\n\n\u00a0\u00a0\u00a0\u00a0}<\/pre><\/div>\n\n\n\n
Python Code<\/strong><\/h4>\n\n\n\n
def LCS(s1, s2):\n\n\u00a0\u00a0\u00a0\u00a0dp = [[0] * (len(s2) + 2) for _ in range(len(s1) + 2)]\n\n\u00a0\u00a0\u00a0\u00a0for i in range(1, len(s1) + 1):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for j in range(1, len(s2) + 1):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if s1[i - 1] == s2[j - 1]:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = 1 + dp[i - 1][j - 1]\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n\n\u00a0\u00a0\u00a0\u00a0sz1 = len(s1)\n\n\u00a0\u00a0\u00a0\u00a0sz2 = len(s2)\n\n\u00a0\u00a0\u00a0\u00a0return dp[sz1][sz2]\n\ns1 = "abcde"\n\ns2 = "ace"\n\nprint(LCS(s1, s2))<\/pre><\/div>\n\n\n\n
5) Kadane\u2019s Algorithms Pattern\u00a0<\/strong><\/h3>\n\n\n\n
This is the easiest pattern. Kadane\u2019s algorithm<\/a> asked directly in the interviews like Amazon. This helps us to find the maximum subarray sum in O(n) time complexity. <\/p>\n\n\n\n
Let\u2019s examine the code for the above pattern.<\/p>\n\n\n\n
C++ Code<\/strong><\/h4>\n\n\n\n
int Kadane(vector<int>& arr){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int mx = INT_MIN;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int current = 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for(int i=0; i<arr.size(); i++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(current >= 0){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0current+= arr[i];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}else{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0current = arr[i];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0mx = max(mx, current);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return mx;\n\n\u00a0\u00a0\u00a0\u00a0}<\/pre><\/div>\n\n\n\n
Java Code<\/strong><\/h4>\n\n\n\n
public static int Kadane(int[] arr) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int mx = Integer.MIN_VALUE;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int current = 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int i = 0; i < arr.length; i++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (current >= 0) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0current += arr[i];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0} else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0current = arr[i];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0mx = Math.max(mx, current);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return mx;\n\n\u00a0\u00a0\u00a0\u00a0}<\/pre><\/div>\n\n\n\n
Python Code<\/strong><\/h4>\n\n\n\n
def Kadane(arr):\n\n\u00a0\u00a0\u00a0\u00a0mx = float('-inf')\n\n\u00a0\u00a0\u00a0\u00a0current = 0\n\n\u00a0\u00a0\u00a0\u00a0for i in range(len(arr)):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if current >= 0:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0current += arr[i]\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0current = arr[i]\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0mx = max(mx, current)\n\n\u00a0\u00a0\u00a0\u00a0return mx<\/pre><\/div>\n\n\n\n
6) Catalan<\/strong><\/h2>\n\n\n\n
In this type of question, we are generally asked to count something like nodes, brackets, etc. For example, in questions like \u201cUnique Binary Search Trees,\u201d we asked to find the total number of unique BSTs.\u00a0<\/p>\n\n\n\n
Let\u2019s understand the code for the above pattern.<\/p>\n\n\n\n
C++ Code<\/strong><\/h4>\n\n\n\n
int catalan(int n)\n\n{\n\n\u00a0\u00a0\u00a0\u00a0vector<int>dp(n+1, 0);\n\n\u00a0\u00a0\u00a0\u00a0dp[0]=1;\n\n\u00a0\u00a0\u00a0\u00a0dp[1]=1;\n\n\u00a0\u00a0\u00a0\u00a0for(int i = 2; i < n+1; i++)\n\n\u00a0\u00a0\u00a0\u00a0{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i]=0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for(int j = 0; j < i; j++)\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i] = dp[i] + (dp[j] * dp[i-1-j]);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0return dp[n];\n\n}<\/pre><\/div>\n\n\n\n
Java Code<\/strong><\/h4>\n\n\n\n
public static int catalan(int n) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int[] dp = new int[n + 1];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Arrays.fill(dp, 0);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[0] = 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[1] = 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int i = 2; i < n + 1; i++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i] = 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int j = 0; j < i; j++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i] += dp[j] * dp[i - 1 - j];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return dp[n];\n\n\u00a0\u00a0\u00a0\u00a0}<\/pre><\/div>\n\n\n\n
Python Code<\/strong><\/h4>\n\n\n\n
def catalan(n):\n\n\u00a0\u00a0\u00a0\u00a0dp = [0] * (n + 1)\n\n\u00a0\u00a0\u00a0\u00a0dp[0] = 1\n\n\u00a0\u00a0\u00a0\u00a0dp[1] = 1\n\n\u00a0\u00a0\u00a0\u00a0for i in range(2, n + 1):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i] = 0\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for j in range(i):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[i] += dp[j] * dp[i - 1 - j]\n\n\u00a0\u00a0\u00a0\u00a0return dp[n]\n\nn = 5\n\nprint(catalan(n))<\/pre><\/div>\n\n\n\n
Conclusion<\/strong><\/h2>\n\n\n\n
We have seen various patterns of Dynamic Programming. These patterns help you to solve most of the Dynamic Programming questions. <\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":14,"featured_media":2537,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-2522","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2522","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=2522"}],"version-history":[{"count":4,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2522\/revisions"}],"predecessor-version":[{"id":7397,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2522\/revisions\/7397"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2537"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=2522"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=2522"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=2522"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}