We are provided with an array of integers that is unsorted and we have to find the longest increasing subsequence. The subsequence need not be consecutive The subsequence shall be increasing Let’s understand that better by a few examples. Example Input [9, 2, 5, 3, 7, 10, 8] Output 4 …
In Decode Ways problem we have given a non-empty string containing only digits, determine the total number of ways to decode it using the following mapping: ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Example S = “123” Number of ways to decode this string is 3 If we …
In the edit distance problem we have to find the minimum number of operations required to convert a string X of length n to another string Y of length m. Operations allowed: Insertion Deletion Substitution Example Input: String1 = “abcd” String2 = “abe” Output: Minimum operations required is 2 ( …
In the maximum product subarray problem, we have given an array of integers, find the contiguous sub-array with atleast one element which has the largest product. Example Arr=[ 0, -1, 0 ,1 ,2, -3] Maximum product = 2 Arr=[-1, -1, -1] Maximum product = -1 Arr=[0, -1, 0, -2, 0] …
Given an array of n integers, find the maximum product obtained from a contiguous subarray of the given array. Examples Input arr[] = {-2, -3, 0, -2, -40} Output 80 Input arr[] = {5, 10, 6, -2, 1} Output 300 Input arr[] = {-1, -4, -10, 0, 70} Output 70 …
In the longest palindromic subsequence problem we have given a string, find the length of the longest palindromic subsequence. Examples Input: TUTORIALCUP Output: 3 Input: DYNAMICPROGRAMMING Output: 7 Naive Approach for Longest Palindromic Subsequence The naive approach to solve the above problem is to generate all the subsequences of the …
In the maximum sum of 3 non-overlapping subarrays problem we have given an array nums of positive integers, find three non-overlapping subarrays of length k with a maximum sum, and return their starting indices. Example Input: nums[] = {1, 2, 1, 2, 6, 7, 5, 1} k = 2 Output: …
In the minimum path sum problem, we have given “a × b” matrix consisting of non-negative numbers. Your task is to find the path from top left to right bottom which minimizes the sum consisting of all the numbers which come in a path you found. Note: You can only move …
“Target Sum” is a special problem for all the DPHolics I have with me today. There ain’t no need to worry I am going to abandon the rest of my lovely readers. We all have gone through the classic KnapSack problem where we try to find the maximum number of …
All about Counting Bits! Humans have a problem communicating with the computers they made. Why? Humans speak and understand the language they have come to speak and listen to over the years but they taught the poor computer 0’s and 1’s. So today, Let’s teach our computer to count the …