Dynamic Programming

Basic Concepts

Problems

Target Sum

Problem Find the number of ways to reach target sum by adding or subtracting the numbers in the array all the elements should be used only ones.

Learning: The most important point here is that we can use dp over the sum as well . Intially we might feel that sum is unbounded but our algorithms complexity will depend on the sum. So we make a dp of size 2*sum+1 rows and n+1 columns. Now index i,j represet that how many solution do we have to reach sum i with first j element of the array. The other important thing is that at any instant we only need 2 columns of the dp array. So we can optimize the space complexity to O(sum).

Solution: Code

Coin Change

Problem Find the minimum number of coins required to make the sum. We can use the same coin infinite times.

Learning: Start by modeling the problem as a backtracking problem. Let’s say we start with amount x and we have d unique coin denominations. So to make x at first stage we have d choices and for each choice we have to make x-c[i] where c[i] is the coin denomination. So we can see that this problem has overlapping subproblems. So we can use dp to solve this problem. We can use a 1D dp array of size x+1. dp[i] will store the minimum number of coins required to make sum i. So we can write the recurrence as dp[i] = min(dp[i],dp[i-c[j]]+1) where j varies from 0 to d-1. We can see that we are using the previous values of dp array to calculate the current value. So we can optimize the space complexity to O(x). Initilize the dp array with large values also corner cases when i-c[j] <=0

198. House Robber Given an array of non-negative integers representing the amount of money of each house. If you rob two adjacent houses then you will be caught. Find the maximum amount of money you can rob.

Learning: We can directly think of a Dynamic programing solution for this question. Let say are at index i and we have to decide whether to rob this house or not. To do that should we need to know the maximum amount of money we can rob from the previous houses. So we can use a dp array of size n+1 where dp[i] will store the maximum amount of money we can rob from the first i houses. So we can write the recurrence as dp[i] = max(dp[i-1],dp[i-2]+nums[i]). We can see that we are using only 2 previous values of dp array to calculate the current value. So we can optimize the space complexity to O(1).

House Robber II

Problem Given an array of non-negative integers representing the amount of money of each house. If you rob two adjacent houses then you will be caught. Find the maximum amount of money you can rob. The only difference from the previous problem is that the houses are arranged in a circle.

Learning: The ideas here is to break the circle and make it into a line. So we can break the circle at index 0 and index n-1. So we can solve the problem for the first n-1 houses and for the last n-1 houses and take the maximum of the two will be our anser.

Maximum Subarray

Problem Given an array of integers find the maximum sum of a subarray.

Learning: We can directly think of a Dynamic programing solution for this question. Let say are at index i and we have to decide whether to include this element in the subarray or not. To do that should we need to know the maximum sum of a subarray ending at index i-1. So we can use a dp array of size n+1 where dp[i] will store the maximum sum of a subarray ending at index i. So we can write the recurrence as dp[i] = max(dp[i-1]+nums[i],nums[i]). We can see that we are using only 1 previous value of dp array to calculate the current value. So we can optimize the space complexity to O(1).

Maximum Product Subarray

Problem Given an array of integers find the maximum possible product of a subarray.

Learning: It is a complicated problem first what we can do is calculate the product of all the subarrays and take the maximum of them. This also is a O(n^2) solution. The key ideas here is that a negative product can be converted to positive with just one negative number multiplication and when we encounter zero their will be no impact of it prefix before zero on the element after zero. So not only we have to maintaine a variable that keeps taks of the maximum product but also a variable that keeps the track of mimimum product. So we can keep track of the maximum and minimum product of a subarray ending at index i. if we see a positive number we can multipy and maxmium product till index i will be the product of all the numbers and the minimum will be the number at index i as the min and max product includes the number at index i. When we encounter a negative number the max prod into the negtive number will become the new min prod and the number it self will become the max prob. This will again switch we see the negative number again. We can see that we are using only 2 previous value of i.e min and max prob we will be able to keep a track of max product till index i.

Longest Increasing Subsequence

Problem Given an array of integers find the length of the longest increasing subsequence.

Learning: We can directly think of a Dynamic programing solution for this question. Let say are at index i and we have to assuming that we know the LIS for all the previous elements. So we can use a dp array of size n+1 where dp[i] will store the LIS ending at index i. So we can write the recurrence as dp[i] = max(dp[j]+1,dp[i]) where j varies from 0 to i-1. This solution is O(n^2) and space is O(n) we can reduce time to O(n) by making a array which keep the track of increasning sequence. Initially we have a empty array when we see first element we put that element into that array now there are two case either the eleme is greater than the elem in array then we just push the elem in array else if the elem is less then or equal to array end we find the appropriate place and replace the eleme using binary search hence at the end of the loop the length of the array will be size of longet increasing subsequence

Longest Palindromic Substring

Problem Given a string find the longest palindromic substring.

Learning: We can directly think of a Dynamic programing solution for this question. Let say are at index i and j and we have answer that index i,j is a palindrome or not. To do that should we need to know wether the substring from i+1 to j-1 is a palindrome or not. So we can use a dp array where dp[i][j] will store whether the substring from i to j is a palindrome or not. So we can write the recurrence as dp[i][j] = dp[i+1][j-1] if s[i] == s[j] else false. The simpler way to do is to exploit the property of palindrom a palindrom has a unique center and we can expand on both sides with i as center we can do it for even and odd length palidrom now the solution is still O(n^2) but space complexity is one.

Word Break

Problem Given a string and a dictionary of words find whether the string can be broken into words from the dictionary.

Learning: This was a hard problem first solution that i came up with was with tries we will do recursive tries traversal and if at the end of the string we landup at a complete word then we can say that the string can be broken into words from the dictionary. This was giving TLE and i had to use @cache decorater which is kind of a tricke to make dp faster.

Let say are at index i and we have to decide whether the substring from 0 to i can be broken into words from the dictionary. To do that should we need to know whether the substring from 0 to j can be broken into words from the dictionary and whether the substring from j+1 to i is a word in the dictionary. So we can use a dp array of size n+1 where dp[i] will store whether the substring from 0 to i can be broken into words from the dictionary. So we can write the recurrence as dp[i] = dp[j] && isWord(s[j+1,i]) where j varies from 0 to i-1. The loop of the j can be futher optimizer by keeping indexes of words till where the words can be made and use j at those indexes only.

Combination Sum IV

Problem Given an array of integers and a target find the number of ways the target can be achieved by adding the elements of the array. Repetition of elements is allowed.

Learning: This is a standard templated problem of dp problem based on sum. We make a dp array of size target+1 x nums now we can further optimize later on. dp[i][j] will store the number of ways the target i can be achieved by adding the elements of the array from 0 to j. So we can write the recurrence as dp[i][j] = dp[i][j-1] + dp[i-nums[j]][j]. The first term is the number of ways we can achieve the target without using the jth element and the second term is the number of ways we can achieve the target by using the jth element. we see that we are reusing the values of j-1 so we can optimize the space complexity to O(target) by using a 1d array.

Decode Ways

Poblem Given a string of digits find the number of ways it can be decoded.

Learning: This problem is similar to the problem of wordbreak now we have to also count the number of ways to make the string as well. The set of symboles are from 1 to 26 so at each index we have 2 choices to take 2 digits or 1 digit. We do the resursion and memoize the result and use them to calculate the result.

Unique Paths

Problem Given a grid of size m x n find the number of ways to reach the bottom right corner from top left corner. You can only move down or right.

Learning: This is a basic matrix dp problem where we are supposed to find the number of ways to reach a cell from top left corner. We can write the recurrence as dp[i][j] = dp[i-1][j] + dp[i][j-1]. The base case is dp[0][0] = 1.

Palindromic Substrings

Problem Given a string find the number of palindromic substrings.

Learning: This is based on the same trick used in longest palidromic substring that palindromic has a center and expand both side and count the number of palindrom

Number of Longest Increasing Subsequence

Problem Given an array of integers find the number of longest increasing subsequence.

Learning: Along with the LIS till each index i we also have to maintain the number of ways to make that LIS and we have to use this ways to count the number of ways to count number of lis.

Partition Equal Subset Sum

Problem Given an array of integers find whether the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Learning: If we have just check if we can make half the sum of the elements from the given elements.

Partition to K Equal Sum Subsets

Problem Given an array of integers find whether the array can be partitioned into k subsets such that the sum of elements in each subset is equal.

Learning: The first checks if the sum of the elements is divisible by k if not then we can’t make k subsets. Now we make a k subset and try out all the possible combination of elements in subset such the weight does not exceed the sum of elements/k.

Best Time to Buy and Sell Stock with Cooldown

Problem Given an array of integers where each element represents the price of a stock on a particular day. You are allowed to buy and sell the stock. One you sell a stock you can’t buy the stock for the next day . An consequtive buying is not allowed i.e ones you buy you have to sell only then you can buy again. Find the maximum profit that can be earned.

Learning: This is a intersting problem because the recurssive solution is relative easy to think. Initially let say we want to buy so for each stock we have to option either to buy or skip ones we buy and from then on we have 2 choices either to sell or skip ones we sell we have only one option skip for the next timestep after that the loop starts from buy and using max function we can write recussion. To convert this to dp we just save the calculated values the uniquie idenfier for each value is its index and the state.