Dynamic Programming 🔥| Coin Change Problem Leetcode | C++ | Java | DSA-One Course #86

Aug 15, 2023

Dynamic Programming 🔥| Coin Change Problem Leetcode | C++ | Java | DSA-One Course #86

Hey guys, In this video we’ll learn about the simple steps to solve any Dynamic Programming Problem. We have been told that solving Dynamic Programming problems is hard But Today I’ll show you how you can learn Dynamic Programming with a simple technique.

Link to the code: https://github.com/Anuj-Kumar-Sharma/…

Practice more questions from here: https://www.techiedelight.com/Categor…

🚀 Follow me on:
Instagram: https://www.instagram.com/Anuj.Kumar…
Linkedin: https://www.linkedin.com/in/sharma-ku…
Twitter: https://twitter.com/realanujbhaiya

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

🥳 Join our Telegram Community:
Telegram channel: https://t.me/coding_enthusiasts
Telegram group: https://t.me/dsa_one

💸 Visit https://www.educative.io/anuj to avail discount on all courses on Educative!

📚 Complete DSA Playlist: • DSA-One Course - The Complete Data St…

Complete Android Development Playlist: • Android Development Tutorial for Begi…

Hashtags:
#anujbhaiya #dynamicprogramming

Track: Chris Henry - Flash

Ignore these tags:

dynamic programming
dynamic programming problems
coin change dynamic programming
dynamic programming java
coin change problem
anuj bhaiya
dynamic programming in java
coin change
what is dynamic programming
making change problem using dynamic programming
coin change problem dynamic programming
dynamic programming tutorial
how to solve dynamic programming problems
dynamic programing
dynamic programming algorithm
dynamic programming c++
anuj kumar sharma
dynamic programming in hindi
anuj
coin change leetcode
anuj bhaiya java
dp
java dynamic programming
making change problem
dynamic
dynamic programming playlist
dynamic programming coin change problem
minimum coin change problem
dynamic programming python
java
dp problems
anuj bhaiya dynamic programming
knapsack problem
coin problem dynamic programming
dynammic programming
anuj bhai
coin exchange problem
dynamic programming geeksforgeeks
greedy algorithm
dynamic programming anuj bhaiya
dynamic programming interview questions
anuj bhiya
apni kaksha
dynamic programming coin change
java anuj bhaiya
coin change dp
dynamic programming hindi
making change problem using dynamic programming in hindi
apni kaksha java
knapsack problem using dynamic programming
anuj kumar
dp programming
freecodecamp
how to master dynamic programming
learn dynamic programming
make change problem dynamic programming
322. coin change
coin problem
java apni kaksha
minimum coin change problem dynamic programming
algorithms
data structures and algorithms
graph data structure
android development
dp tutorial
dynamic programming for competitive programming
dynamic programming in python
dynamic programming questions
graph
how to solve dp problems
longest palindromic substring
recursion
0-1 knapsack problem dynamic programming
aditya verma dynamic programming
anuj apni kaksha
bfs
coin exchange problem in dynamic programming
coin tower
dynamic programming anuj
dynamic programming javascript
graphs
java by apni kaksha
knapsack
leetcode 322
python dynamic programming
recursion in java
sieve of eratosthenes
unbounded knapsack problem

Content

0 -> Hey guys,

0.427 -> see this,

1.515 -> tell me how many circles are there.

6.943 -> Tell me the no. of circles,

8.437 -> so you can count, 1, 2, 3, 4, 5, 6, 7.

11.496 -> There are 7 circles here.

13.086 -> Now tell me the no. of circles,

15.064 -> I've added one circle here,

16.315 -> now tell me how many,

17.346 -> So you already know there were 7, I just added one more,

19.897 -> that means there are 8 circles here.

21.31 -> How did you know that,

22.32 -> because you stored in your memory that there were 7 circles before,

26.686 -> this guy just added a new circle,

28.282 -> so there are 8 circles here.

30.063 -> You did...

30.73 -> When I added this circle you did not count again

32.527 -> it completely,

33.502 -> because you already the result before and the result it will be.

36.921 -> This is called memorization,

38.551 -> and this is what's used in Dynamic Programming,

41.104 -> this is the concept which makes Dynamic Programming efficient, memorization.

45.496 -> And today we'll learn how Dynamic Programming works,

48.358 -> how we get to know if a question is of Dynamic Programming,

52.283 -> and the steps to solve it.

54.429 -> Let's start.

63.344 -> Hey what's up guys Anuj here,

64.59 -> and in todays video we are going to talk about

65.443 -> Dynamic Programming.

66.824 -> You must have heard this word, DP, quite a lot

70.053 -> and with it you heard that it's very difficult, you don't know what to do.

74.02 -> And it is set in beginner's mind that it's a very big thing,

77.816 -> and they are always anxious, when they learn it,

80.703 -> they start to memorize it,

81.761 -> with which they are not able to grasp it's concept.

85.96 -> So it gets set in our mind that Dynamic Programming is a very difficult thing,

89.429 -> but in today's video I am gong to tell you some little steps

92.276 -> which you will get to know,

95.318 -> after that you will not get afraid from Dynamic Programming.

98.367 -> Dynamic Programming is not a big thing,

100.53 -> we will get to know how it's solved,

102.549 -> basically it's a recursion, it is solved in

104.875 -> a recursive way.

106.541 -> We just use a memory in it,

109.5 -> through which we break a problem in smaller problems,

113.273 -> that is what recursion does,

114.565 -> but we store the result of those smaller problems,

117.546 -> so that if we again get that smaller problem,

120.612 -> if we encounter it again

122.221 -> then we just return the result of that small problem.

124.491 -> See what I am trying to say,

126.088 -> so basically I am making a picture,

128.522 -> suppose this is the big problem,

130.503 -> P, is the big problem,

132.828 -> and this problem can be broken into smaller problems,

135.3 -> suppose it can broken into three smaller problems,

138.451 -> p₁, p₂, and p₃.

140.087 -> So if this big problem can be broke into three smaller problems,

142.581 -> then we can say that we need p₁, p₂, and p₃ to get the result of P.

146.9 -> And if p₁ also has similar structure,

150.1 -> if it can also be broken into smaller problems,

151.774 -> p₂ and p₃ as well,

153.442 -> then we say that this problem has a substructure.

158.589 -> This problem is becoming a substructure.

160.815 -> We can also say subproblem,

161.874 -> this is the problem, and this problem is becoming subproblems.

164.867 -> Solution of this type of question,

166.46 -> where we divide a problem,

168.895 -> into many different parts,

170.788 -> and then solve it,

172.061 -> that's what we call divide & conquer.

173.754 -> Divide & Conquer is in merge sort,

175.245 -> in merge sort, you divide an array into two part, solving them separately.

180.064 -> And do the same with the divided arrays.

183.031 -> You divide it again,

184.583 -> same with the other one,

185.728 -> you go like this until it cannot be broken.

189.28 -> After that you solve it.

190.18 -> That's what we call Divide & Conquer.

191.659 -> What happens in Divide & Conquer is,

194.023 -> the subproblems made, don't have any relation between them,

197.497 -> all of them are independent,

198.457 -> that means we have to solve each of them,

200.48 -> you have to go to each one and solve them,

202.137 -> solve p₁, p₂, and p₃.

204.073 -> And give their result to P.

206.686 -> But the special thing about Dynamic Programming is that

209.016 -> these smaller problems do have a little relation between them,

212.917 -> meaning, they overlap with each other,

215.443 -> they are not like this,

218.028 -> they overlap a little.

224.336 -> You can see, p₁, p₂, are overlapping like this,

226.595 -> similarly suppose p₂ and p₃ are overlapping,

234.343 -> So this is the overlapping area,

237.943 -> and this, we take advantage of this,

240.838 -> and optimise the problem a little.

242.764 -> How?

243.433 -> What we do is,

244.568 -> solve p₁ completely,

246.23 -> so p₁ is this whole,

249.115 -> so we solved p₁ completely,

250.687 -> but when go solve p₂, then we will see

252.939 -> this part of p₂, we've already solved this

257.276 -> so we don't need to solve that again.

259.073 -> So we will store that in a memory,

261.788 -> we have a memory,

263.077 -> where we keep p₁,

265.098 -> this is the result of p₁.

266.443 -> We see in p₂, in problem 2,

269.307 -> we are already getting some of the result of p₂ in p₁.

272.183 -> Have we already solved it,

273.819 -> yes we have, so we will just return it from p₁

276.37 -> don't compute it again.

277.526 -> Can you understand that,

278.91 -> so when you think that this problem has overlapping subproblems,

283.805 -> there Dynamic Programming is used,

286.367 -> and you don't get this in the beginning,

288.997 -> but when we do enough problems in it,

291.009 -> because we get using the examples

294.26 -> this is how it's applied, this is the big problem and this is the small problem.

296.491 -> We will see now,

297.177 -> with examples, how it is done.

299.362 -> So you must have understood,

300.127 -> first of all, Dynamic Programming,

302.375 -> and Divide & Conquer,

305.023 -> we understood what's the difference between them.

307.86 -> In Divide & Conquer also we divide

309.684 -> but all the problems are independent,

312.775 -> but in Dynamic Programming, the problems

314.668 -> have overlapping subproblems between them.

316.843 -> That is there are some parts in them which overlap

319.011 -> which we store in the memory,

321.151 -> and that is how we are optimising it.

324.71 -> Now let's see some examples,

326.31 -> suppose this is the question,

328.298 -> I told you,

330.903 -> I have given you some coins,

332.329 -> in denomination,

333.218 -> that means, the coins that you have

335.789 -> those will be 1 rupee coin,

338.021 -> or 5 rupees coin or 7 rupees coin.

340.068 -> It doesn't exist, I know that,

342.041 -> but suppose the coins that you have,

343.806 -> there are many, 1 rupee coin,

345.673 -> many 5 rupees and 7 rupees coins.

349.122 -> And I am telling you,

350.712 -> make 18 rupees.

352.391 -> With minimum number of coins,

354.362 -> so how can you do it.

356.47 -> Some of us, what we'll do is,

358.477 -> make two coins of 7 rupees,

361.082 -> because 7 is seen to be the largest,

362.667 -> we'll take two coins of 7 rupees,

363.698 -> it will be 14 rupees,

364.999 -> and after that the remaining four will be from here,

367.569 -> four will be from here, 1 times 4.

371.18 -> So this will be 18.

373.061 -> So the total no. of coins used in that are

375.169 -> two of 7,

378.084 -> and four of 1.

379.888 -> Adding them, 4+2 is 6,

381.901 -> here we are using 6 coins.

383.702 -> And we call this approach Greedy approach,

386.338 -> where we already think how the problem is going to be solved.

390.091 -> We already know,

391.938 -> this is the way that we have to take.

393.565 -> This is greedy approach,

395.406 -> we know every time the way we have to go on.

398.146 -> Without any computation,

399.456 -> and how do we know,

400.553 -> I chose 7 one time, so that means from 18, only 11 is left,

407.039 -> now I know again I am going to choose 7,

410.556 -> choosing 7 from 11,

411.681 -> remaining are 4 rupees.

412.902 -> I can see that neither 5 nor 7 can fit

414.847 -> so I have to choose 1 four times.

417.316 -> So I have the fixed the path here,

419.742 -> this is called greedy approach,

420.852 -> But here greedy approach is failing,

423.608 -> how is it failing,

424.965 -> see here,

426.415 -> you are using total six coins,

428.364 -> but instead if you use this,

429.963 -> use 7 rupees coin one time,

432.001 -> two 5 rupee coins,

433.806 -> how much is it,

435.059 -> it's three coins,

436.515 -> and use 1 rupee coin one time.

437.88 -> So we can do our work using 4 coins.

440.731 -> Instead of 6 coins.

442.08 -> Here the better and optimized solution is,

445.799 -> use one coin of 7 rupees,

447.794 -> two coins of 5 rupees,

450.047 -> and one coin of 1 rupee,

451.889 -> total there will be 4 coins

453.917 -> when there were 18 rupees here.

457.758 -> Now thinking this is a bit difficult,

460.197 -> how do you think like this.

463.195 -> We can think about this one,

464.961 -> every time just pick the maximum no.

467.995 -> But this is the greedy approach

469.793 -> and this approach does not work sometimes,

471.287 -> sometimes it does work,

472.157 -> We could see those solutions, how intuitive they are

474.251 -> this is how it will be done.

475.206 -> But here it is failing,

477.361 -> so let's see how this way is working here.

481.994 -> How this is working here,

483.277 -> and how you can apply the Dynamic Programming approach from here.

485.818 -> How you can make subproblems from this problem

488.622 -> which overlaps.

490.197 -> Every time we have to in Dynamic Programming,

492.053 -> can the problem become subproblems which overlaps.

494.848 -> Sometimes minimum and maximum are asked,

497.528 -> always optimisation type problems occur.

499.778 -> There's always something to optimise in this.

502.795 -> In greedy also you have to optimise

505.038 -> but in this you have multiple ways,

508.304 -> and you have to choose one of them.

510.646 -> In greedy, we know where we have to go

512.58 -> this will be solution.

513.905 -> In Dynamic, we have to calculate at every step,

516.911 -> and select one of the ways where we have to go.

522.662 -> So this is the difference between them,

524.092 -> let's see how this problem gets changed in Dynamic Programming.

527.813 -> Suppose you need to make 18 rupees,

530.351 -> and you have the same coins, 7, 5 and 1 rupees.

534.611 -> You have these three coins,

535.612 -> you have to make 18 rupees.

537.215 -> I am saying you have three ways,

539.183 -> right now you can see in the future,

542.361 -> you don't think that it will require 4, 5 coins,

547.583 -> think that you can think about the future,

551.577 -> after that, what we have to do,

553.841 -> move one step forward in the future,

556.263 -> moving one step in the future,

557.809 -> we need to go to 18 rupees

559.322 -> but what we'll do is use 7 rupees,

562.062 -> and if we have used a 7 rupee coin

564.04 -> 7 removed 18 lefts you with 11 rupees,

566.092 -> now the problem is smaller,

568.118 -> now I just have to tell for 11 rupees,

570.222 -> and similarly the coins are the same,

571.941 -> 7, 5 and 1.

573.959 -> We have the same coins,

575.419 -> so I'll again write 7, 5, 1.

578.04 -> so if we used 7,

579.911 -> then we came to 11,

581.532 -> think about not using seven,

585.161 -> you chose 5,

587.459 -> 5 removed 18 gives you 13,

590.66 -> that came when we used 5.

593.239 -> And maybe you did not use 5 and used 1.

597.551 -> Now 1 removed from 18 will be 17,

601.202 -> you used 1.

602.925 -> Now you are one steps ahead in the future,

605.614 -> but we won't stop there,

606.783 -> now we have to go further,

608.023 -> now you have to move ahead more in the future,

609.624 -> one more step forward.

611.255 -> So the step you took first,

613.019 -> move one more in this.

614.826 -> Choose 7 again from 11,

617.689 -> 7 removed from 11 gets 4.

622.128 -> Choosing 5 from 11 will remain 6,

624.068 -> Choosing 1 from 1 remains 10 rupees.

626.398 -> this is 5 and this is 1.

629.007 -> You have moved one more step in the future,

631.475 -> similarly do that here,

633.436 -> move one step ahead in the future.

634.908 -> We got 13 using 5 rupees,

637.832 -> now think using 7,

639.802 -> 7 removed from 13 will be 6,

642.388 -> 5 removed from 13 is 8,

645.687 -> and 1 removed 13 is 12.

648.616 -> Now what we'll do is,

650.18 -> do the same procedure in this.

653.563 -> So 5 removed 17 will be 12,

657.888 -> 7 removed from 17 will be 10,

662.471 -> 5 removed from 17 is 12,

664.5 -> and 1 removed from 17 will be 16.

667.051 -> Now we are two steps ahead in the future.

671.233 -> And we have to repeat the same thing,

674.269 -> we'll move ahead like this,

676.656 -> until the coins,

679.322 -> the rupees that we want to make it,

680.843 -> gets 0.

682.931 -> Less than 0 is not a concern,

684.901 -> until it get 0, we have to keep moving like this.

687.929 -> And after that we'll return the result.

689.508 -> But you can see here, some problems are repeating themselves

692.138 -> there's 6 rupees here and here as well,

695.807 -> just as 12 is here and here also.

699.089 -> Similarly 10 is in two places,

702.441 -> So what you solved one time for this,

705.186 -> after coming from 5,

706.897 -> you have to do the same thing coming from 5,

710.476 -> What you do with 6 coin from 5 here,

713.473 -> will be done here too.

716.336 -> So you can see,

717.682 -> you are solving the question again.

723.276 -> And here the problems are overlapping,

725.859 -> this problem,

728.054 -> and this problem are overlapping.

730.664 -> You can see 6 is coming in both of them,

732.536 -> so calculate 6 for this one only,

734.432 -> don't do it for this one,

735.747 -> just store the result of this 6 in a memory

739.776 -> and say that it is the answer of 6,

743.739 -> and when somewhere else there's a need for the answer of 6,

747.014 -> then you'll check whether the memory has 6's answer,

749.385 -> if there is then return that from the memory,

752.462 -> you won't need to do the steps below it,

755.757 -> because you have already that calculation here.

758.628 -> You'll do the same for 10 and for 12,

761.484 -> so you don't need to find again,

764.485 -> the answer for 12 has already came here,

766.879 -> that's why there's no need to find the answer for 12 again.

769.536 -> In this way, you optimise your problem,

772.708 -> and you must have understood how the overlapping substructure works.

777.13 -> And this is why we say there's memorization in Dynamic Programming.

781.699 -> And this was simply Dynamic Programming,

784.142 -> nothing else.

785.598 -> Basically this is a recursive problem,

787.499 -> but since we used memory here

789.579 -> that is why it is now Dynamic Programming.

791.213 -> People explain it using the fibonacci series

794.418 -> that is a very basic approach

797.256 -> many things don't get cleared in that.

799.685 -> That's why I used a little complex,

801.341 -> this is not even that complex,

803.062 -> I hope you understood how the problems are breaking into subproblems.

808.643 -> One more thing,

810.185 -> here every problem is breaking into three problems

813.983 -> that's why,

815.204 -> it'll go to O(3ⁿ).

818.112 -> Since these are 3 here,

820.515 -> and every part is breaking into three,

821.928 -> This is what the time complexity of the problem would have come, 3ⁿ.

828.105 -> Earlier.

830.439 -> Maybe three are given to you in the question,

833.779 -> there are just three coins,

834.947 -> but sometimes it might be that there are 'm' coins,

838.375 -> so it could go up to mⁿ.

841.137 -> It can go to mⁿ.

842.542 -> mⁿ means a very big time complexity.

845.926 -> But what will happen here is,

848.576 -> when we've done like this,

849.902 -> then we won't go into the same problem again,

852.019 -> we are not going again for 6, 12, 10,

856.223 -> so you will see, we will prove this too,

857.729 -> how it will convert from (mⁿ) to O(m.n)

864.441 -> so that is a huge optimization,

867.281 -> only because we are using space and Dynamic Programming.

870.826 -> So let's see,

872.179 -> how this working through code,

874.118 -> and then we'll understand it's concept more.

876.134 -> How Dynamic Programming is working.

877.879 -> Alright.

879 -> So I am inside Eclipse

880.346 -> and I've made a package named Dynamic Programming,

883.321 -> this is class inside it,

885.923 -> all this code is available to you,

887.892 -> I'll give you the link where you can see all this code,

890.561 -> I'll create a function,

892.392 -> static and we'll name it 'mincoins',

896.109 -> this will take a number, how much rupee coin you want to make,

900.477 -> that is how many changes you want to make,

903.915 -> and it'll take an array which will be denomination,

907.258 -> this is the array,

908.663 -> and that's it, for now we'll go ahead with just this.

911.856 -> So this is a static array,

914.659 -> it's a static method in which the program is int,

918.548 -> what we have to do now is,

920.496 -> this will be a recursive function,

922.313 -> and we already know how recursion works,

924.208 -> first of all we need to handle base cases,

926.372 -> then solve the recursive subtext.

929.471 -> This might be a little different for you,

931.398 -> since we are going to use recursion in it,

933.019 -> with for loop.

934.111 -> So this was a request too, how to do recursion using for loops,

936.866 -> so we'll learn that today,

938.304 -> how to do that.

939.508 -> First of all let's see the base case,

940.842 -> if 'n' is 0,

946.6 -> then return 0,

948.565 -> that means,

949.626 -> you are told that,

952.871 -> how many coins of 0 rupee will be there,

957.167 -> so if you want to do for 0, then for 0 coins you'll have 0 rupees.

960.831 -> So it has a simple answer, this.

963.487 -> But now it is said,

965.581 -> it's not 0,

966.906 -> how are you going to move forward now,

969.557 -> you will run a loop in this array,

972.011 -> see, we are going here one time, here and here.

974.447 -> We are doing the same thing here, recursive leap of faith.

977.688 -> We just have to solve for this, this and this,

980.521 -> what's happening outside and below it

983.38 -> is not our concern.

985.825 -> Recursion will handle all that.

988.674 -> We just need to solve this step,

990.615 -> whatever's running below will be solved automatically

992.695 -> using Recursion.

993.774 -> If you want to deep dive into it, then I'll show that too,

996.217 -> but we just have to focus on this step,

998.473 -> all other steps are handled by recursion on it's own.

1000.853 -> Let's see how they'll be done.

1002.237 -> In the first step, we are running a loop

1004.295 -> going through this whole array, which is the length of the array,

1006.924 -> and we are using this one time,

1008.787 -> then this one and then this.

1010.011 -> And the minimum answer from these three,

1012.075 -> we'll return that.

1013.662 -> The minimum of the three answers.

1015.582 -> So the spreading in the tree

1017.473 -> will have one way which will give minimum number

1020.997 -> we have to return that one here.

1023.868 -> This will be the solution to the problem.

1028.112 -> Let's see how it will be done,

1029.618 -> first of all I'll create a loop,

1031.905 -> for int i equals to 0,

1034.673 -> i less than a.length,

1037.838 -> i++.

1040.005 -> So what I am doing is,

1041.243 -> I have created a loop in this array,

1043.26 -> now,

1044.871 -> we'll do,

1049.343 -> int subanswer,

1050.603 -> what's the answer of the subproblem,

1052.171 -> the answer for subproblem is mincoins.

1056.821 -> n-ai, and a.

1061.998 -> See what I did there,

1063.441 -> I went to the subproblems now,

1065.517 -> from here I went to this subproblem,

1067.357 -> removed 7 from 18,

1069.423 -> I got 11 and 11 is the problem now,

1071.859 -> now I'll do the same things for 11.

1074.028 -> Subanswer will handle these things,

1076.242 -> but there are still some things here which we should handle,

1078.899 -> first of all n-ai,

1080.984 -> this can go less than 0,

1083.42 -> there might be that you have a big denomination,

1085.983 -> maybe you have a 7 rupees note,

1088.558 -> but you just want to make 6 rupees.

1090.035 -> So you'll do 6-7, which will be -1,

1093.454 -> so we don't want that.

1094.454 -> To not get those cases,

1095.682 -> we'll do, if

1097.203 -> n-ai,

1100.378 -> if it ever,

1101.772 -> is greater than or equal to 0,

1105.471 -> then we should move ahead in this.

1109.914 -> We need to do this thing only when

1111.517 -> n-1 is greater than or equal to 0.

1117.205 -> So from here we'll get the subanswer.

1118.807 -> Now we'll check

1119.637 -> I'll create an answer variable,

1123.586 -> so I'll create an int answer,

1124.818 -> which I'll start with,

1126.676 -> interger.maxvalue.

1129.714 -> So I've started this variable using interger.maxvalue.

1132.703 -> Now I'll check,

1134.15 -> if the subanswer,

1139.402 -> plus 1,

1140.591 -> if I add 1 in the subanswer,

1141.903 -> if this is smaller than answer,

1144.47 -> then the answer should be subanswer,

1148.15 -> plus 1.

1149.865 -> Let's understand what I did,

1151.026 -> I basicallly went here, here and here also,

1154.558 -> and I, first of all came here,

1157.325 -> removed 7 from 18, 11,

1159.683 -> and some answer came from here,

1161.559 -> I returned that answer here,

1163.655 -> and I checked this subanswer,

1167.9 -> is this answer smaller than the current answer,

1171.098 -> if it is smaller than the current answer then it will be accepted,

1173.697 -> else it will not be accepted,

1174.878 -> and I am also adding 1, why,

1177.166 -> because the problem here was for 18 rupees,

1180.6 -> the problem here is made for 11 rupees,

1182.982 -> so adding 1 in 11 rupees answer so that 18 rupees answer can come,

1188.046 -> because I used 7 coin here,

1189.21 -> I used this coin here,

1190.245 -> used one coin,

1191.059 -> that's why the plus 1.

1193.573 -> I am doing the same thing for everyone of them,

1195.558 -> and the minimum among them,

1197.497 -> will be returned.

1199.687 -> This is what is happening here

1200.685 -> and finally I did that...

1209.443 -> Return answer,

1210.801 -> we returned the answer,

1212.548 -> and this thing will run now,

1215.27 -> and here we are doing that,

1216.539 -> until now I've not used any DP,

1218.86 -> Dynamic Programming is not used anywhere till now,

1220.387 -> we are not using a memory anywhere,

1221.998 -> basically we are travelling everywhere,

1223.693 -> checking for everyone,

1225.519 -> and let's see how it works.

1228.051 -> First of all let's run it,

1230.285 -> int answer,

1232.092 -> let's make something before,

1233.936 -> let's make int 'n',

1235.57 -> n is 18 in this case,

1237.923 -> and we will also create an array,

1240.056 -> array is 7, 5, 1.

1243.888 -> It can be in any order,

1244.985 -> it should not matter.

1246.557 -> Sorted or not,

1247.794 -> doesn't matter.

1249.092 -> this is array,

1251.533 -> after tha, answer would be mincoins,

1257.86 -> n and a.

1260.388 -> We'll print this,

1264.277 -> Let's try to run it,

1267.459 -> Here 4 is coming,

1269.617 -> and 4 is the correct answer, we even checked it,

1271.439 -> 4 comes when you use 7,

1273.742 -> then two times 5,

1274.899 -> and one time 1.

1276.039 -> How does the path come out,

1277.462 -> you used 7 so the value becomes 11,

1279.908 -> after that you used 5,

1281.157 -> 5 removed from 11 is 6,

1282.822 -> 6 is made,

1283.893 -> after that you will again use 5,

1286.228 -> so used 5 here,

1287.751 -> and 5 removed from 6

1289.689 -> will be 1,

1292.15 -> and removing 1 from 1 will give you 0,

1294.968 -> and as soon as it becomes 0, it will return

1296.582 -> this will return 1,

1298.048 -> then this 1 will go up,

1299.284 -> and this will return 1+1, 2,

1301.365 -> then it will again go up,

1302.732 -> 2+1 would give you 3,

1304.266 -> and 3+1 going up will give you 4.

1306.413 -> And you will say 4 is the minimum answer.

1309.298 -> Elsewhere there will be different answers but

1311.225 -> from this path you'll get the minimum answer.

1314.725 -> That's why 4 was returned here,

1317.383 -> there are many other paths, but

1318.765 -> they won't give you the minimum answer.

1321.453 -> So this was the path through which you got the answer,

1324.153 -> but let's see now how Dynamic Programming can in this,

1326.321 -> because we needed to solve again and again,

1328.181 -> for this path 6, then again for 6 here,

1332.249 -> here solved for 10,

1334.146 -> then again solve for 10, 12.

1335.926 -> In this way, you'll find a lot of problems if you go deep in this,

1338.981 -> which are overlapping,

1340.704 -> it is solving for everyone.

1342.644 -> We need to tell it to stop, if it has already saved the answer,

1345.986 -> then don't solve it again.

1348.162 -> For that we need to create an array,

1350.112 -> and let's do this, this 18 here,

1352.11 -> so we'll create an array of length 18,

1354.503 -> where we will tell at every index, what's the answer

1357.226 -> If we have already found the answer for 6,

1359.321 -> then we can tell the answer of 6,

1362.074 -> whenever it asks for 6,

1363.437 -> we will say we already have the answer for 6,

1365.579 -> don't compute for that again.

1367.481 -> How can we solve that,

1369.049 -> I'll create an array, named dp,

1372.691 -> and

1374.206 -> new int,

1375.316 -> I'll keep this array's size to be n+1,

1379.533 -> The size of the array is n+1,

1380.795 -> and I'll fill this array, arrays.fill,

1384.159 -> -1 in this dp array.

1388.255 -> -1 will depict that we have not gotten the answer for this.

1391.843 -> And, like this base condition here,

1394.389 -> we will have to tell it a base condition,

1397.199 -> the answer at dp's 0th index is 0,

1401.306 -> like you did it here,

1402.479 -> do that here also that dp's 0th is 0.

1405.118 -> Else it will just keep running all the time in it,

1407.453 -> it will never find the answer,

1409.166 -> so dp's 0th is 0,

1410.956 -> we have to pass this dp array now,

1412.474 -> I'll pass the dp array,

1414.996 -> the array is here,

1416.43 -> pass it here, dp,

1418.229 -> and similarly it will be called here,

1421.021 -> so here also I'll pass dp.

1423.465 -> Now let's see how we are going to use this dp array,

1426.036 -> you'll see, how this question will turn from normal recursion to Dynamic Programming.

1431.987 -> And how it will convert from mⁿ into m.n.

1436.345 -> Let's see how it is done.

1437.569 -> So I'll say that you are getting the subanswer like this

1440.248 -> but first check, do all the subanswers exist,

1442.663 -> for this value, n-ai.

1445.321 -> So what I'll do is,

1447.957 -> first let's take int subanswer,

1450.484 -> it's value will be 0,

1452.168 -> we'll check whether in dp

1456.634 -> has n-ai,

1459.926 -> is it there or not,

1461.149 -> does it have an answer or not,

1462.463 -> that is, if it's -1,

1466.002 -> if this is not -1,

1467.406 -> that means the answer already exists,

1468.855 -> then the subanswer would be this,

1473.528 -> dp of n-ai.

1481.349 -> That is if you already have answer for 6,

1484.917 -> if 6's answer is not -1,

1486.485 -> then don't calculate the sub answer,

1489.024 -> it's answer would be this,

1490.856 -> what we have already stored in this.

1492.873 -> But if it's still -1, then we will have to solve that.

1497.557 -> We will solve it,

1499.773 -> when it is not already stored.

1505.065 -> So this will be here,

1506.885 -> I'll set it up,

1508.959 -> so I have done just that here,

1511.252 -> if it's already stored in dp,

1513.578 -> it's already stored in the array,

1514.782 -> then just pick it up from there,

1517.802 -> if it's not stored, then you will have to calculate for that.

1520.242 -> Where are we filling the values from in this dp,

1522.66 -> whenever we return the answer

1524.418 -> before that we fill the value in dp,

1527.653 -> dp of n will be answer.

1533.13 -> Either write this, or

1534.59 -> we can remove this line, and write here,

1537.274 -> return dp of n equals to this,

1543.022 -> saving one line isn't going to make a difference.

1546.046 -> So this was it,

1546.785 -> here the dp is working,

1549.343 -> whenever you are returning the answer of a subproblem,

1552.624 -> like the 6's answer you returned,

1554.236 -> you have to store that in the dp as well,

1557.738 -> because you with great effort did the calculations below it

1560.638 -> so you'll store 6's answer in the memory.

1563.52 -> So you'll go up,

1564.421 -> and when you return, you'll check whether in dp

1566.867 -> the position 6 is -1 or not,

1568.41 -> you'll see it's not -1 it's filled,

1570.908 -> now there's no need to go down,

1573.022 -> just return whatever here was from the dp array,

1577.684 -> and this is the same thing happening here.

1582.802 -> Even now it will give 4, we'll run it.

1586.084 -> It is getting 4 even now.

1587.681 -> But I'll show you one thing, what's filled in the dp array.

1592.589 -> for...

1596.9 -> Do you see what the array's printing,

1599.058 -> the array is basically returning 18 values,

1601.952 -> not 18, it's 19 values.

1603.719 -> 0 at 0th index,

1605.095 -> 1 at index 1,

1606.065 -> and every value is telling us

1606.937 -> how many coins you need to make this much.

1609.916 -> To make 18 rupees you need 4 coins,

1612.278 -> to make 1 rupee you need 1 coin,

1614.394 -> that 1 rupee coin,

1615.579 -> to make 2 rupees you need two coins,

1617.259 -> two 1 rupee coins.

1618.072 -> Three coins for 3 rupees

1619.25 -> four coins for 4 rupees,

1620.238 -> for making 5 rupees you just need one coin.

1622.813 -> So there's only one coin at 5th index.

1625.177 -> And why we need only one coin,

1626.011 -> because 5 rupees coin already exist.

1628.274 -> To make 6 rupees you just need two coins,

1630.312 -> one 5 rupees coin and a 1 rupee coin.

1632.329 -> You just need one coin to make 7 rupees

1634.295 -> because 7 rupees coin already exists.

1636.199 -> We are moving in this way,

1638.206 -> and in this way, the algorithm is n.m instead of mⁿ.

1643.139 -> Let's see that also, how it is happening,

1644.273 -> let's see how, so it will be clear.

1647.931 -> Because the calls are the same,

1649.303 -> but the calls are not the same, we've reduced some,

1652.717 -> how did we do that, let's see,

1654.06 -> so, we've stated that if dp of n-ai is -1,

1658.494 -> then take the minimum coins if it's -1,

1662.979 -> but if it's not then return it from there,

1665.035 -> that means this minimumcoins call,

1667.601 -> how many times will it be called, at maximum.

1671.175 -> You can see this will be called at maximum, n times.

1676.787 -> So you have to call it n times here,

1678.882 -> and why is it so,

1680.379 -> because if for 5 rupees already exists in the dp,

1683.754 -> then you don't need to call below, for 5 rupees,

1686.448 -> but if it doesn't exist for 5 rupees,

1688.073 -> then you will have to call,

1689.124 -> same for every n.

1690.973 -> From 0 to n, you have to check for everyone,

1693.516 -> suppose there's i in between,

1695.975 -> for that if it exists in the array,

1698.587 -> then you don't need to call but

1700.337 -> if it doesn't exist then you will have to call.

1701.666 -> at most you have to call it n times.

1706.951 -> This minimumcoins call,

1708.601 -> and you are running a loop,

1711.151 -> a.length, for m times,

1712.945 -> if size of a is m,

1714.68 -> then you are running this loop for m times,

1716.463 -> and you are calling n times,

1717.95 -> so time complexity becomes n times m here.

1720.725 -> And if we see space complexity,

1722.484 -> it's O(n), a linear space complexity.

1726.498 -> Because we used space,

1727.794 -> that's why the time complexity which was very big got smaller.

1731.177 -> We are using space to save time complexity,

1734.045 -> we can call this a space-time tradeoff.

1737.124 -> But basically this is Dynamic Programming,

1739.871 -> now these thing, you can show in a 1-d array,

1743.217 -> there are more complex problems in which we store in 2-d arrays.

1746.545 -> One time we see that there's no need to store in even 2-d array,

1749.089 -> there's too much space used,

1750.677 -> so we'll show it using a map.

1753.869 -> We create a hashmap, to show the values.

1756.304 -> Basically we need to use memory,

1758.558 -> through which we can save time,

1759.512 -> you can see it anyhow.

1761.34 -> This is basically Dynamic Programming,

1763.575 -> and I hope you understood how it basically works,

1766.019 -> we also saw this code

1767.89 -> and many times there are doubts,

1770.386 -> how recusion is done using loops,

1771.987 -> we saw that today also,

1773.014 -> I hope that is clear to you now,

1774.591 -> we'll move into more Dynamic Programming in the upcoming videos,

1778.451 -> we'll see more problems, how they work.

1781.451 -> There's a very famous problem in it, 0/1 Knapsack,

1783.923 -> where most of the concepts of DP are based on that.

1788.95 -> so we'll understand how that works,

1791.244 -> how we store Dynamic Programming in a 2-d matrix,

1793.729 -> apart from that

1794.453 -> I'll provide you the resources, you'll find the links below

1796.994 -> where you can practice Dynamic Programming questions.

1800.938 -> So this was it in today's video,

1802.673 -> I hope you liked this video,

1804.253 -> Like this video, Subscribe the Channel, Give it your support,

1809.401 -> and I'll meet you in the next video,

1811.122 -> in which we will talk about advanced problems of Dynamic Programming.

1814.268 -> So I'll see you in the next video, till then,

1817.243 -> Bye, Bye!

Source: https://www.youtube.com/watch?v=-NTaXJ7BBXs