Introduction to Dynamic Programming | Greedy vs DP

本站添加: 2026-05-17

[00:00:00]Hey everyone, I hope you all are safe and doing good. So today I'm going to start one of the most important topics in DSA that is dynamic programming. Many students fear it because of its name dynamic programming and they feel that it's tough but that's not true. It's not tough. It's just a another way or you can say algorithm paradigm or a technique to solve problems like we have discussed gritty divide and conquer. You have binary search you have branch and mount your backtracking. Same it's an algorithm design technique. Yeah, a little bit tricky but once you get the base of dynamic programming, you are done. It's really easy for you. But prerequisite for this is to understand dynamic programming or DP is what you need to understand recursion first.

[00:00:45]So if you haven't watched my recursion videos, please go and complete that chapter first and then come to this because if you don't know recursion, you will not get it. Once you are good in recursion, it will be really easy for you to get dynamic programming. Okay. So that is prerequisite to understand DP.

[00:01:02]Now what is DP? I've told you it's just a technique or algorithm paradigm which is used to solve which problem?

[00:01:10]Optimization problems. You know what is optimization problem? Greedy technique is used to solve optimization problem.

[00:01:19]We have discussed this thing. What are optimization problems? A problem which is having many physible solutions.

[00:01:27]There's a problem P having many many solutions. Out of these few solutions are physible solutions right and from these physible physible solutions you have to get the best solution or you can say the optimal solution.

[00:01:41]So the problem will have only one optimal solution and the goal is to find out that solution. This problem will be having what constraint some constraint will be given to you plus objective.

[00:01:55]Some constraints is given some objective you have. Objective is either to maximize or minimize. Maximize or minimize. There are two kind of optimization problem. Maximization or minimization problem. This thing we have seen in detail uh in in that video introduction to greedy algorithm. And to solve these kind of problems optimization problems we have many techniques like greedy, dynamic programming, branch and bound backtracking. So greedy we have already discussed. Now we see dynamic programming and how dynamic dynamic programming is different from greedy. So what is exactly the approach your dynamic programming is I'll discuss in this lecture. Okay, you understand? Now this is a technique which is used to solve optimization problems. It's a problem which is having many physible solution. Out of these physible solutions your goal is to find out the best or optimal solution best in the form of maximum or minimum. like you have to find out shortest route, minimum time, uh maximum efficiency, maximum effort or minimum cost and [clears throat] these kind of problems.

[00:02:55]These are optimization problems, right? Okay. Now, how grey solve these problems? Greedy approach. Greedy approach was what? At every stage, at every point, we choose the we choose the best uh choice or we can say we take the locally something like this. We choose locally at that time the best option or the best candidate and we just hope that we move forward and we just hope that it will lead to a global optimal solution like shortest path from uh A to B like there are many routes there are many routes through which we can go from A to B. You have to find out shortest path. So what we do from A I can go to this to this to this. So whichever this at this point I am at this point source.

[00:03:49]So the shortest whatever the shortest distance I will select that I'm greedy here. So suppose this is 10 kilome this is five this is 20. So this one is shorted. So I will choose this. I'll move forward at this point. Now from this point suppose I can go to here I can go to here I can go to here or here or here.

[00:04:07]Now whatever the shortest I will again choose that. Suppose this is one out of all these shortest. So I will choose this path. Then suppose this is also again one which is shortest. So I'll choose this path. So like this at one particular point wherever you are I will take some I will select what the minimum ultimately you have to find out the shortest distance or whatever the shortest distance from a to the next vortex where you can go that I will select. So you are being greedy but it doesn't guarantee that it will further works that it will definitely lead to the optimal solution. It is not a guarantee. So greedy approach what works for optimization problems but not for all problems.

[00:04:50]Okay that thing we have seen in coin problems.

[00:04:54]Now how dynamic programming works. See you know you have some physible solutions and if I say one thing how you can get the best out of all the possible physible solutions or possible solutions.

[00:05:08]I will find out all the physible solutions and then compare all the physible solutions or possible solution you can say and then choose best.

[00:05:17]Will you get the best or optimal solution? Yes, definitely.

[00:05:22]But the thing is if you go with this approach that you find out all the possible solutions, physible solutions and compare them and then find out the best for sure you will get best solution but it's time consuming. Yes, it's time consuming. So that's kind of approach DP programming follows. Yes. To somewhat I'm not saying exactly dynamic programming finds all the possible solutions, compare them and find out the best. No, not exactly like this.

[00:05:51]Indirectly indirectly it tries to find out all the possible solutions and select the best one at last. So somewhat it is following this approach DP programming. So that's why DP will give you correct result for sure. Best one optimal solution DP will give you. Okay.

[00:06:12]So to sum what I guess that this idea is clear to you but DP will make it faster will make it faster. That's why DP is a great approach by taking some decisions at every point. Okay, that we will see when I solve the problem you will get this thing. Okay, just an general overview what is DP and how DP is different from grey approach. Let's take one example. Suppose uh you want to go from your home to office.

[00:06:41]Your home is here. You want to go to office, right?

[00:06:47]So at some point at some point it says that you are at a signal. So you are following greedy approach. You are following greedy.

[00:06:57]So it says that a road going to left right now at this point of time it will take 5 minutes.

[00:07:07]Okay. A road going to right it will take 10 minutes.

[00:07:13]So if you are being greedy so you will choose definitely this greedy technique will choose this. Okay this is shortest having less time and you have to reach from your home to office in minimum total time. So we'll take this this path. But maybe maybe this will have a traffic jam later of 30 minutes.

[00:07:32]So total time will be 35 if you choose this route. And in this route if you take right now it is little bit slower.

[00:07:40]This route is right now faster but later have traffic jam. This route is right now slower but later there's no traffic jam. Suppose traffic is only for 5 minutes. Traffic jam you'll traffic you will get only for 5 minutes or 10 minutes. So this will give you a total of only 20 minutes.

[00:07:56]But because you are greedy, you chose this one because locally right now at this point of time at this signal what is best for me I will choose that what is best at that I will choose that one. I don't care about future consequences and past.

[00:08:12]No, I'm being greedy at this point of time that I guess you know but ultimately it leads to you have to give 35 minutes and this route if you would have chosen it will be 20 minutes that's greedy but if same thing if you apply DP if you apply DP then see how DP works DP will check [clears throat] that okay that's five plus later future consequences also DP will see which take decisions that okay later the traffic exam is 30 so it will become total time 35 minutes later in this route traffic exam is only 10 minutes it will take me 20 minutes so using DP you will choose this so at every point DP is also going to solve the problem in stages in stages means divide the problem in sub problems and like that and every step on every stage some decision will be taken okay like Here I decide later traffic jam is only 10 minutes right now maybe it is slower but totally it will be optimal for me so I will choose this.

[00:09:21]So it takes into account the future consequences or other other things also and then decide using DP DP technique uh you know follow this approach then decide. So at every point some decisions are taken and then ultimately you will reach to optimal solution. Okay. So DP is going to solve problem in stages and every stage some decision is to be taken and ultimately it will lead to a optimal solution only if only if whatever decisions you have taken those are optimal. So the decision must be optimal at every stage at every step you decide something you take decisions so those decision must be optimal then only you will get optimal solution.

[00:10:08]So that's main approach of DP in greedy at every point we select some but here we decide we decide based on like other factors as well.

[00:10:23]So decide here we decide means uh basically try to analyze all the physible solutions and then we prepare some data and then decide because obviously to take some decision if you want to decide something uh something like this suppose uh there is a road and it's a having three lanes three lanes and here also there is a cut suppose uh there is a cut this road is going on. So basically like uh you can turn you can you just go ahead and you can turn and this is also a road and vehicles are coming in this way. From this we are going in this way.

[00:11:06]Okay. So suppose person A is in this lane. Person B is A is here and suppose B is here or kind of that or maybe A or B both are here.

[00:11:20]So sometimes it happens that when we are in this lane so this lane it seems that this lane is going faster right so what B will do B will decide that okay this lane is going faster so B will switch to this lane to this lane okay but A is not going to switch because B is griding this lane is going faster I have to reach faster so I'll switch to this lane but the thing is in this lane most of the vehicles are those who wants to take this cut take this cut and sometimes it happens the road the traffic on this road is also like heavy heavy so the vehicles are not going to not are not able to take this turn so quickly so that's why they stuck here they stuck here now this lane is stuck and B is stuck here but this lane obviously is going simply forward forward forward so A will go like this but because of greediness B stuck stuck here. Yes. But why B was that's A was like following DP programming. A is not greedy. A is able to decide that okay I will not switch in this lane because A knows after some after some time or after some distance there is a cut. So most of the vehicles are those who want to take cut in this lane and sometimes it's not easy or it's not quick to take this cut and I want to go straight. So better to stay in this lane or this lane like that. Okay. But A was able to decide this thing because A knows about this cut. So in dynamic programming I have told you that at every stage some decision is to be taken right. So we take into account how how decision can be taken. How you can decide something?

[00:13:03]If you have information then only you can take if A knows this thing that there is a cut and a smart enough so he can uh he can decide. So for taking decision we need data or we need information that's really important the role of data or the information is really important in DP programming maybe B doesn't know that there is a cut soul he took this uh turn or this lane right so that's why DP prepares data as well while solving question you will get this thing you will get everything whatever I'm saying in this video once we are we will start solving questions don't worry if you're not getting these things you just take an overview but you will get about DP everything everything about whatever I'm saying in this video once once we solve a question so DP prepares data generates data generally in table data to take decisions prepared data while solving question take decisions and ultimately at every stage decision will be taken and ultimately it will lead to an optimal solution. But the condition is the decision must be optimal at every stage.

[00:14:16]The decision must be optimal. If if the decisions are not optimal, it will not lead to an optimal solution.

[00:14:22]That's basic or you can say main approach of dynamic programming. And while preparing this data, the stabular data DP consider all these possible solutions or physible solutions then ultimately it will give you an optimal solution. I've told you now that's how indirectly it is it is checking all the physible solutions and get the best one because DP prepares data and while preparing this data it consider all these physible solutions. Okay, that's why I'm saying that DP means in greedy we directly we directly go to an optimal solution. We don't care about we don't explore these physible solution. don't care about that because we are being greedy at every step at every stage and we just hope that we will lead to an optimal solution. So we directly go to that optimal solution but in second case in DP I've told you find out all the physible solutions compare them and then find out the best solution. So that's kind of approach DP is following but not exactly finding all the possible solutions. It's not obviously feasible.

[00:15:23]It's very timeconuming. Okay. But while preparing data, the stabular data which will help DP to take some decisions, optimal decisions at every stage. While preparing this data, it consider all the physible solutions.

[00:15:39]So that indirectly it's like it can uh monitor or it can you can say um generate or it can you can say like u or I would say indirectly like this DP checks all the possible solutions compare them and find out the best solution. So to somewhat the approach is clear to you and this thing that the decision at every stage must be optimal to get a optimal solution. This is known as principle of optimality.

[00:16:11]Principle of optimality and DP follows this principle.

[00:16:19]Although it is written in some other words in algorithm books that is optimal substructure. Okay. But that is principle of optimality. Principle of optimality means principle of optimality says an optimal solution to a problem contains optimal solutions to its subpros. So it's like if you are going suppose the shortest route you get from your home to office as you go to a some intermediate location then b then office that's the shortest route you get using dynamic programming from your home to office. Okay. Now it says that the principle of optimality it says that the best path from your home to office is this using DP. So the best path from A to office must be shortest path. The best path best path from B to office. B to office must be shortest.

[00:17:24]The best path from A to B from A sorry A to C must be shortest. That is what principle of optimality says. If suppose this from A to C from A to C the path is not optimal.

[00:17:39]It's not shortest. So you find out some other route from A to C you have to go to A to C. You find out some other route which is shortest which is shortest than this one from A, B, C. Suppose from A, D and C. This is shortest.

[00:17:56]It means the original solution from home to A to B to C to office. This was also not optimal.

[00:18:04]Right? Optimal solution that's a big problem. Home to office optimal solution to the problem to a problem contains that is for sure optimal solutions to its sub problem. Sub problem is what?

[00:18:17]From home to A that is a sub problem.

[00:18:18]From A to B, that is also a sub problem.

[00:18:21]B to office that is also a sub problem.

[00:18:23]Main problem is home to office.

[00:18:26]So all these sub problems must have optimal solution. If suppose A to C is not best is not best or the shortest path. So there is some other path A to D which is shortest. So definitely the original path from home to office is also not also not optimal.

[00:18:43]Not shortest, not best.

[00:18:46]And this rules DP follows. This is principle of optimality rule. Okay, I think it is clear to you. But in books it is written note in the form of principle optimality. It is written that DP uh problems must have two conditions.

[00:19:03]Means the problem have two conditions.

[00:19:05]Then only you can use DP to solve those problems. And what are those? What are those condition? First is overlapping sub problems and optimal substructure.

[00:19:19]So DP is an optimization technique. It is used when a problem has these two conditions overlapping subpros and optimal substructure. This optimal substructure is nothing but the same thing which is principle of optimality.

[00:19:32]We have discussed optimal substructure means we use optimal results of sub problems to achieve the optimal solution of a bigger problem. And why DP use this approach uh this principle of optimality? Because in DP we find out the solution of bigger problems or the big answer using small small answer solving small problems. So if the smaller answer is answer is not optimal how you can get the bigger answer optimal. So the smaller answers must be optimal. So if you are able to divide because basically we divide the problem into sub problems in DP that's what the main idea. So if those small sub problems should have optimal solution then only you can get a global optimal solution. Okay the problem must have these two things that is optimal substructure. What is this overlapping sub problems in divide and conquer technique? I have told you that if we divide divide and conquer means we divide the problem into sub problems but these sub problems should be independent. These should not be overlapping. If these are overlapping, we use DP.

[00:20:35]If these are independent, we can simply use divide and conquer technique.

[00:20:38]Overlapping sub problem means what? See, let's take one example. Uh you know, you are very well aware about that Fabini series. How to find out Fabini series? I guess you know this thing. If I start writing this like 0 then one. First two are 0 and one. Then add this and this then 1 1 + 1 2 2 + 1 3 5 8 13 and like this. This is fabic series. Yes. So if I say find out fib of um six fibonic series of six you know recursively how you can solve because we have already done this. What is the formula to solve? We write f of n or fib of n is f of n -1 plus f of n -2. That's how we solve that's the recursive method or the formula to write down this thing. Okay, you get this thing because we have we discussed this thing when we were discussing recursion.

[00:21:36]So you can go and check out this thing.

[00:21:37]Now this thing is if you draw the recursive tree of this. So fib of six.

[00:21:43]So basically fib of n minus one that is five and we call four n minus 2 that is four but that's recursive call. So first we call this and we further move this while going backward these right call recursive call will be evaluated right.

[00:22:00]So this is f of n minus one that is four and f of three this is now we go in this direction again f of 3 and f of 2 again this is f of 2 and f of 1. f of two will be f of 1 and f of zero. Now we stop because f of 0 is one and f of sorry f of 1 is one and f of 0 is zero. So just add these two and it becomes one. f of 2 is 1. It is 1. So 1 + 1 is 2 like this.

[00:22:31]Like this when we when we reach to dead end then we come back. Now after f of three right direction f of two. So this will be expanded f of 1 again f of 0.

[00:22:42]This will give me 1. This will give me 0. So 1 + 0 is equal to 1. So it will give me 1. 2 + 1 is 3. So it will give me three. Yes.

[00:22:51]Now when we go back but right direction is right part right recursive call is still left. So we expand this. So when we expand this it becomes f of two. F of 1. So again expand this f of two it becomes f of 1 f of 0. f of 1 it's 1 it's zero. So 1 + 1 it's 1 it's 1. 1 + 1 it's 2 and 3 + 2 it's 5. And then we explore this right direction that is f of four. Then we explore f of four. It means f of three and f of two. f of three is f of two and f of one. Again f of two is f of one and f of zero. That's how basically we draw recursive uh tree. That's how we do. But what is the problem here?

[00:23:38]Can you see? See for f of six we have divided this into sub problems. That is find out first f of five and f of4.

[00:23:44]These are sub problems. Yes. But to find out f of five, we again divide it. f of four and f of three. So these are sub problems. f of four, we have again divided f of three, f of two. So these are sub problems. These are sub problems. Are these overlapping? Yes.

[00:24:01]See you see here. See check this. f of three multiple times we are calling this method passing same passing same argument passing same parameter same data that is three same argument that is three f of three is here here here see multiple times if I say f of two it's here here here many times I have f of two so it means these are overlapping these sub problems are overlapping.

[00:24:37]Yes, we can solve. Overlapping means um it's not independent. They are not independent.

[00:24:44]They're overlapping because same sub problems, same sub problems is solved multiple times. Is solved multiple times. See, same sub problems is solved multiple times. So that is kind of overlapping sub problems. Now whenever we say whenever you find out this end, we go to dead end. So we get f of two is one. Yes. But can I do this thing again?

[00:25:08]If you I go back here. I go f of2 rather than expanding this rather than calling f of two. Can I use the same one here?

[00:25:16]Because I have already calculated f of2.

[00:25:18]Why you are calculating again f of2? Why you are calculating again f of2?

[00:25:25]But in recursion you have to calculate it. Yes. So we can do one thing. What?

[00:25:30]Okay. Store these results.

[00:25:33]and use here one directly don't call it don't call it use one while we are going back f of three will become two so suppose when we go back here we are calling f of three don't call it have you f of three previously computed f of three this sub problem yes and the result have you stored yes I have stored so directly use it to here don't call it so this tree will not be expanded see how easy this will E yes so this is nothing but dynamic programming dynamic programming one approach of dynamic programming I'll see there are two approaches of dynamic programming but that is one and like when we are storing this something like this this is known as memorization memorization okay but don't worry I'll tell you this thing in next lecture that's just I I would just want to give you that this example these are the kind of overlap overlappinging sub problems. If the same sub problems you have to solve multiple times multiple times in the same question to get the to get the answer of bigger problem then that are overlapping problems.

[00:26:43]So if a problem is having these two conditions or these two characteristics that it will have overlapping sub problems and it has optimal substructures okay that you can divide the problem into sub problems and recursively you can find out the optimal solutions of these sub problems. This will ultimately lead to optimal solution of the main problem.

[00:27:02]So that is kind of optimal substructure of a problem. We say this thing in that case you apply DP to solve that problem. So yes, Fabenic series you can use recursion plus you can use DP that's kind of a DP problem. You can use your DP to solve this.

[00:27:22]It will optimize the recursion because in recursion there are multiple calls.

[00:27:27]But if you if you save these answers so directly no need to call further this directly use the stored value. So it will drastically improve the time complexity. It will reduce suppose in this case time complexity is 2^ n.

[00:27:44]So it will drastically may be reduced to order of n in some polomial form it will give you. So it's kind of one more aspect of dynamic programming or one important point you can say about a DP is what it is optimization of recursion.

[00:27:58]Yes it is optimization of recursion in DP also we are going to break into sub problems. So recursively we are solving these sub problems. Okay. So recursion we need but it's not compulsory that DP means you have to use recursion only.

[00:28:13]There is some other approach also that also we'll see. Okay. to somewhat overview of DP is clear to you. What is DP? How DP is different from GD? It is to u it is used to solve optimization problems. What are optimization problem?

[00:28:28]How this is different from grey? Uh at every stage DP try to solve problem in stages. At every stage it decide take some decisions and uh that optimal decisions and those decisions you will lead to an optimal solution. The decision must be optimal to get an optimal solution ultimately. Okay. To take decisions we need data. So DP prepares while DP prepares while solving question DP generates or prepare data as well. Considering all the physible solutions and then find out the best optimal solution at last.

[00:29:01]So that's important to understand about DP. Okay. Now in the next lecture I will tell you what are some approaches to solve question DP approaches or two techniques. two techniques to solve problems. Okay, so that's it for this lecture. Now watch the next lecture.

[00:29:18]Till then, bye-bye.