DYNAMIC PROGRAMMING PRACTICE PROBLEM | DSA Course | GeeksforGeeks

Hello everyone. Welcome back. So, in this video, we will solve some interesting problems on a dynamic programming. So, let us start with one of my favorite problem, another count bits problem. So, in this problem, for a given integer n, you have to print the number of set bits in each integer from 1 to n. So, for n is equal to 5, this is the expected output. So, let me explain you the sample input and output first. So, for a given integer n, you have to print the number of set bits in all the integers from 1 to n. So, for n is equal to 5, integer 1, the binary representation of 1 is 0 0 1. I'm writing in terms of 3 bits. Then for 2, 0 1 0. Then for 3, 0 1 1. For 4, it is 1 0 0. And for 5, it is 1 0 and 1. Cool? So, how many set bits are there? 1. Then the number of set bits, again 1. Then the number of set bits, 2. Then the number of set bits, 1. Then the number of set bits is 2. So, this is the expected set of outputs. So, what is the naive solution? So, the naive or the brute force approach is very straightforward. That is, iterate over all the integers from 1 to n and then count the number of set bits in integer i. So, write a function count bits for integer i, and this function will return return you the number of set bits in integer i. And I'm assuming that you guys are already familiar with the bit manipulation basics, and you can simply write this function in log of i base 2 time. So, then I will simply return this integer, that is, number of set bits in integer i. So, what is the time complexity? So, the time complexity is n, as we are iterating over all the integers from 1 to n, that is, n iterations, and then log of i base 2 time. And the The of this i is up to n. So, it is log of n base two. So, this is the time complexity and can we do something better? And yes, definitely we can do something better. And the idea here is to use a dynamic programming. So, let me just quickly define a state which is the first step for my state. So, let's say DP of I as the number of bit number of bits an integer an integer I. So, to solve this problem using a dynamic programming, you just need to know about two operators. That is left shift operator and a right shift operator. So, what is the value of A left shift B? Isn't it A multiplied by two power B? And what is the value of A right shift B? So, it is A divided by two power B. Cool? So, let me just quickly write in this way. So, let's say 13. So, the binary representation of 13 is 1 1 0 1. 8 + 4 and plus one. So, then what is the value of 13 left shift one? That is we shift all the bits one position in the left hand side and a one zero will be added in the place of a LSB. So, one zero one 1 1 0 1 and a zero will be added. So, this is nothing but a 26. That is a 13 multiplied by two power two power one which is equal to 26. And how I can write my 27? So, that is 13 left shift one and plus one. That is 1 1 0 1 and instead of zero, now we are having 27. That is one. So, how many number of set bits are there? So, the number of set bits here are three and there is no change because we have just performed a left shift operation and that is added a zero on the left hand side. Sorry, on the right hand side in the place of MSB. So, we have added an extra zero. That is there is no change in the number of set bits. So, this is remain three and here the zero has been changed to one. So, it is four. That is 3 + 1, which is equal to four. So, can I write in this way? That is, can I write on this recurrence relation? DP of I, it is equal to DP of I by 2 and the plus one. That is, the number of set bits in I is equal to the number of set bits in I by 2. If I is completely divisible by completely divisible by 2, otherwise we add one if I is odd. So, if I mod 2 is equal equal to one. So, if it is odd, then I will add one. And if it is even, then the number of set bits in I is exactly equal to the number of set bits in I by 2. That is, the number of set bits in 26 is exactly equal to the number of set bits in 13. Because we have just performed the left shift operation, that is, added a zero on the right-hand side. Cool. So, this is the recurrence relation and the base case, if I is equal equal to zero, that is, the number of set bits in zero, and DP of zero equal to zero. So, yeah, this is the state recurrence relation and the base case. Let me just quickly code this up. So, take an integer N from the user, then my DP array. So, int DP of size N plus one. DP of I is number of set bits in integer I. And here I'm writing a bottom-up solution. You can write a top-down, that is, recursion plus memorization by yourself. So, DP of zero is equal to zero. Then I iterate over all the integers from one to one to N, and DP of I is equal to DP of I by 2 and a plus one if I is odd. So, that is, I and one. So, if I is odd, then I and one is equal to one. So, we are adding one in my answer. And if I is even, then I and one is equal to zero. That is, we are adding zero in my answer. So, this is something that we want. You can also write a if condition, if odd, add one, otherwise nothing, add zero. But, this is the smarter way of implementation, and I will print the value of DP of I, that is, number of set bits in integer I. So, let me test for N is equal to five. So, for N N is equal to five, this was the expected output. Cool. And the time complexity is linear, O of N, and uh the extra space that we are using is also linear because of this DP array. So, this was all about uh this problem. Let's just solve the next problem, which is minimum steps required to reach N. So, you are given a positive integer N, and you have to reduce reduce it to one by performing the following steps. So, the first step in the first step or operation, you can reduce N to N minus one. Other and uh the second operation where you can reduce N to N by two if N is divisible by two. The third type of operation where you can reduce N to N by three if N is divisible by three. So, definitely, we have to minimize the number of operation that we perform to reduce N to N by N to one. So, for N is equal to 16, the expected output is four. That is, reduce the 16 to eight, then eight to four, four to two, and two to one. So, pause the video and try to think of a solution, and first try to find a greedy solution, and if your greedy solution is not working, then explore all the possible paths, and uh write a formal state, and then write a recurrence relation. If there is an overlapping subproblem, then memorize it using dynamic programming. So, our goal is to reduce N reduce N to one. So, it's not always it's not always about to directly start with a dynamic programming solution. Just write a greedy solution, propose some greedy solution, and check your greedy solution is correct or not. and the best way to correct yourself uh that the best way to prove yourself correct is to prove that you are not wrong. So, for your greedy approach, propose some for your proposed greedy approach, write some test cases, and check your test cases will pass your greedy approach will pass that test cases or not. And if you find some test cases for which your greedy approach is not working, then update your greedy approach. And if you if you still find some test cases where your greedy approach is fail, then try to recursive solution. That is, explore all the possible configurations and find the best solution. So, for we have to reduce n to 1. So, for 16, what I can do? I can use the operation of second type n to n by 2 because it is divisible by 2. Then again, n to n by 2. Then again, n to n by 2. And again, n to n by 2. So, how many operations we require? So, 1 2 3 and 4. So, in this case, my answer will be 4. So, what is the best greedy solution that might came to your mind? The best greedy solution is that we have to reduce n to 1. So, we try to reduce n as much as possible. That is, we give n to n by 3 as the first This is my first priority. Then the second priority, and otherwise we reduce n to n minus 1. Cool? So, the best greedy approach is to reduce n to n by 3 if it is divisible by 3. And if it is not divisible by 3, then check for check for n by 2. So, that is if n mod 3 not equal to 0. Cool? Then I try to divide it by 2. And if it is still not divisible by 2, that is, n mod 2 not equal to 0, then I had no other option, so I will reduce n to n minus 1. But this greedy solution this best greedy solution would not work for all the cases. So, let me just give you a give you an edge case for n is equal to 10. This greedy approach would not work for n is equal to 10. So, for 10, what you can do you will first check for n by 3. So, not divisible, then you will check for n by 2. Divisible, so we'll divide it by 2. 5. Then we check for then this is the new value of n. So, again I will check for n by 3. Not divisible, n by 2. Not divisible, then n minus 1. Cool. 4. Then for this 4, not divisible by 3, divisible by 2. So, we'll reduce it to 2. Then for this 2 not divisible by 3, but divisible by 2. So, reduce it by half. So, it is 1. So, this is the greedy path. And if you follow this greedy path, then you claim that your answer is equal to 4. That is the minimum operation that we require. One operation, two operation, three operation, and a fourth operation. Cool. But, you can memorize this operation that is number of operations equal to further. That is, you can reduce 10 to 1 by just using three operations. And let me tell you how. So, first reduce this 10 to 9. And then this 9 to 3. And this 3 to 1. So, you can see in this case you just only require three operation. So, this was the greedy path, and this was the best path. So, the greedy solution the greedy approach would not work pass for all the test cases, and here is the corner case. So, now we do not have any other option except to explore all the possible paths. Now, let me just quickly form my state. So, let's say f of n as the minimum number of steps required to reduce n to 1. Then what will be the recurrence relation? So, f of 1 f of n is equal to f of n by 3 plus 1, and definitely we call this function if and only if n divisible by 3. So, that is n mod three is equal equal to zero. The other option that I had, that is I will explore every path. Let's say it is 12. So, I will divide it by two, that is six. We'll divide it by three, which is four. And I will also reduce it to n minus one because there might be case where n minus one path is the best one. So, yeah. I will reduce I will try all the possibilities. So, then n by two and since I have performed one operation, so we'll add one here. And definitely, if n is divisible by two, then only I will call this function. n mod two is equal equal to zero. Otherwise, f of n minus one. Cool. Add plus one. And since my goal is to minimize the answer, so I will take minimum out of all the three possibilities. And what what would be my base case? That is f of one. So, the number of steps required one required to reduce one to one. Isn't it zero? The minimum number of steps required to reduce one to one. Zero, right? And now you know the state definition of a state, a recurrence relation, and base case. So, let us simply code this up. And again, I'm going to write a bottom-up DP. You can implement the top-down DP, that is recursion plus memorization by yourself. So, simply taking this integer n as input and then my DP of size n plus one. Then DP of one is equal to zero. For i is equal to two till n. So, first I will initialize DP of i with some maximum value. And then I will check whether it is divisible by three or not. So, if it is divisible by three, then DP of i is equal to minimum of DP of i {comma} DP of i by three and plus one. Since we have performed one operation. Then don't write else case because we have to explore all the path. So, not else, but if only. So, if I mod 2 is equal equal to 0, then DP of I is equal to minimum of DP of I that we had got so far, and DP of I by 2, and plus one. Cool. And for I minus one, we don't have to check anything. And finally, I will print DP of N, which is my answer. The minimum number of steps required to reduce N to one. So, let me just quickly test for 16. The expected output was four. Yeah, four it is. Then, for 10, the expected output is three. So, we got three. And what is the time and the space complexity? So, the time complexity in this case is linear since we are iterating from all the integers from one to N. So, linear time. The extra space that we are using is this DP array, which is again linear. Cool. So, this was all about this problem. Let just move on to the last problem of this video, which is our partition problem, a rod cutting. So, again, I would highly recommend you guys to pause the video, read the problem, and try to think of a solution. So, given a rod of length N, and array pieces, prices of length N, denoting the cost of cost of pieces of of rod of length one to N. And we need to find the maximum We need to find the maximum amount that can be made if the rod is cut optimally. So, for N is equal to four, this is the expected output. So, this is the final problem of this video, rod cutting, which is very similar to the previous problem. So, I highly recommend you guys to pause the video, and read the problem statement, try to think of a solution. So, given a rod of length N, and an and array prices of length N, denoting the cost of pieces of rod of length one to n. So, we need to find the maximum amount that can be made if the rod is cut up optimally. So, for n is equal to four and this prices array of length four, the expected output is 20. Here, one base indexing has been considered. That is prices of one. Here, one is the index is representing the cost of length of rod one. Prices of two is representing the cost of rod of length two and so on. So, let me just quickly explain you the sample input and output first. So, we have a rod of length four. So, how we can cut this rod? The one way is to cut this rod into four chunks of length one each. So, one, one, one, and one. So, then what would be the cost in a cut cost? So, one, {comma} one, {comma} one, {comma} one. So, the cost of rod of length one is three. So, that is four into three, which is equal to 12. Cool. What is the other way to cut this rod? We can cut this rod into two two chunks of length two and two each. So, two and two. Then, the inner cut cost is two into five, because the cost of rod of length two is five. So, two into five, which is equal to 10. Cool. The other way is to cut a rod of length three, rod of length four into two chunks, one of one and three. So, in this case, the inner cut cost of one {comma} three is three. Three plus four, which is equal to seven. And if you cut the rod into three and one, then the inner cut cost would be same. So, one and three and three and one both will give you the same result. Then, finally, we can we do not cut this rod. So, in this case, the inner cut cost is 20. Because the rod of length four is having price 20. And since our goal is to maximize the amount, so the maximum here is 20. That's why the expected output is also 20. So, hope the problem statement is clear to everyone. So, this is the dynamic programming solution. Any greedy solution would not work here. You can try it try it by yourself. So, let me just quickly formalize state. So, let's say DP of n as the maximum amount that can be made. The maximum amount that can can be made by rod of length of length n. So, what is dynamic programming? It's basically memorization of a state. So, we explore all the possibilities for every state. And if there is an overlapping subproblem, then just simply memorize it by either using top-down DP or a bottom-up DP. It's totally up to you. And this time I will code the top-down DP. And the bottom-up DP is for you. That is iteration. Top-down is recursion plus memorization. So, if this is the definition of my state, then what will be the recurrence relation? So, let's say you are given a rod of length eight. So, let's say the rod of length eight. And let me also write a prices array of length eight. So, the price of rod of length one, let's say it is two. Then what price of rod of length two, let's say it is four. Then five, seven, then maybe three. And let's say six and 10. Cool. And this is seven integers, then the rod of length uh eight, let's say it is having price 12 maybe. So, what will be the recurrence relation? So, for DP of eight, what I can do? I can cut this rod. Basically, I have to explore all the possibilities. So, from this rod of length eight, I can cut it into two parts, that is I can extract extract a rod of length one from here and then this is the remaining sub problem. That is what is the maximum amount that I can make from rod of length seven. So, can I say this thing? DP of eight, it is equal to price of one. Let me write P. So, here I'm writing P in place of this price. So, P of one. And here I'm considering one base indexing, you can consider zero base indexing. But uh yeah, it's totally up to you. So, P of one and uh plus DP of seven. I have extracted extracted a rod of length one from here, then this is the remaining sub problem. Cool? Then the other option that I have extract a rod of length two and then the remaining problem sub problem, which is the maximum amount of maximum amount that I can make from rod of length six. So, remaining sub problem. So, price of two and uh plus DP of six. The maximum amount that I can make from rod of length six. Cool? And so on for three, four, five, six, and seven. Then what I can do, I cannot cut this entire rod. That is this rod would remain as it is. So, in this case price of eight plus DP of zero, right? So, this would be my base case. And and since our goal is to maximize the answer, so I will take maximum out of all the possibilities. Cool? And this is my base case if the value of n is equal to zero. What if the value of n is equal to zero? So, in this case what is the maximum amount that I can make? So, the maximum amount that I can make is also zero because no rod, no price. Cool? So, now you know the state, you know the recurrence relation and uh you know the base case. So, try to implement the solution and let me just quickly again summarize it. So DP of N DP of N it is equal to summation of from 1 to N and maximum of DP of I not DP of I but actually the price of I plus DP of N minus I Cool. And yeah, this is the base case. So let me just quickly code this up. And how I come up with this recurrence relation? So DP of N the maximum amount that I can make here basically this is just a summary. So the maximum amount that I can make from rod of length N. So then here I have I will iterate over all the possible values of I that is possible values of rod which I can extract from the rod of length N. So it is from 1 to 1 to N. Then if I cut a rod of length uh I from N then this is the remaining length of remaining length. So DP of N minus I and uh I will get the price corresponding to it. So yeah. So let me just start from the very scratch. So simply I'm taking an integer N. Then here I will make this uh a price array as a global global array and uh even it's not recommended to make uh things global but since this is an educational video so that's why I'm writing this array globally. So assuming the standard the standard limit so constant int N as 10 power 5 because generally the size of the array that will be given to you in most of the problem is around 10 power 5. So one followed by five zeros and plus something plus some constant just to be on the safer side to do not go out of bound. So 10 power 5 plus 5. So yeah. And uh for the current N let me just quickly take zero base indexing or one base indexing. And one more thing the global arrays are initialized with a zero, not with the garbage values. So, DP of zero is equal to or DP, not DP, but price of zero is equal to zero. Cool, so I will start taking the input from one. So, I is equal to one while I is less than or equal to n, I plus plus, seen price of I. That is rod of length, price of rod of length I. Cool, and then I will simply print rod cutting. So, this is a recursive function. And here I will pass the current value of n. That is the current length of rod. So, it is initially n. I wanted to know the maximum amount that I can make from n. So, int rod cutting and int n. So, if n is equal to zero, then simply return zero. No rod, no price. Otherwise, what I can do, I can iterate over all the possible lengths and extract I from here. And I will initialize my answer with zero. So, answer zero. And then answer is equal to max of answer comma price of I and plus rod cutting of n minus I. So, this is the recurrence relation. And finally, I will return this answer. So, let me just quickly test it for the given input 3 5 4 20. So, n is equal to 4 and 3 5 4 20. Here the expected output was 20. So, here this is it is same as the expected output. And this is a recursive code. Now, let just analyze that whether there is an overlapping subproblem or not. So, yes, there is an overlapping subproblem. Because if you draw this recursive tree that from here, what you can do from rod of length seven, you can extract a rod of length rod of length one and then solve the problem, remaining subproblem. So, this DP of seven, so here what I can do I can can a rod of length one from this rod of length seven. So, that is price of one and then solve the remaining sub problem. Plus TP of six. Cool. So, if you have noticed this sub tree and this sub tree going to be exactly same. So, isn't it there is an overlapping sub problem? So, there is an overlapping sub problem. So, definitely I'm going to memorize the answers. So, enter memo and of size n. Then mem set will set every value every index value to minus one. So, three parameters are required for this mem set function. Base address, minus one and size. So, size of memo. So, first I will check whether I have already computed this answer or not. So, if memo of n not equal to minus one, that is it is not equal to the default value. So, we have already computed the answer for this state. So, simply return it. So, return memo of n. Otherwise, compute the answer, store it and then return it. So, let me just build this program one more time. And yeah, we got the same output. So, what is the time complexity? So, the time complexity for a recursive functions, let me just give you a general idea to find the time complexity for recursion. So, time complexity of recursion So, it is equal to number of different states, number of different states or you can say different function call multiplied by time complexity of each function. of each function. So, for this case, the time complexity the overall time complexity, how many different function we are having? So, we have memorized the answer. So, how many different values of n? So, isn't it n? The initial value of n. So, it is n into n. And why this n? Because this is the number of different functions, but the time complexity of each recursive function of each function is also n because we are having this loop from 1 to n. So it is n squared. This is the time complexity. And what is the extra space complexity? So the extra as an extra space we are using this memo array. So it is also of length n. Cool. So this is all about this video. We have solved the three problems on dynamic programming. So yeah, thank you so much guys for watching this video.