Watch this lecture if you find the concepts discussed in this video to be unknown: ua-cam.com/video/_OPJaU2Xz7o/v-deo.html. Basics of DP have been covered in this video.
Approach 2 is just the reverse of approach 1. Approach 1: state: dp[i] = number of ways to reach a sum of i transition: dp[i] = sum(dp[i-1], dp[i-2]... dp[i-6]) base case: dp[0] = 1, as number of ways to generate 0 is just 1 final subproblem: dp[n] as we finally want to find the number of ways to get n Approach 2: state: dp[i] = number of ways to go from i to n transition: dp[i] = sum(dp[i+1], dp[i+2]... dp[i+6]) base case: dp[n] = 1, as number of ways to go from n to n is just 1 final subproblem: dp[0] as we finally want to find the number of ways to go from 0 to n What's the issue you faced in implementing?
Let's finish this one off first and then we can plan more content. We also have our upcoming TLE 9.0 course coming up in December 1st week that you can explore in case you're interested in other topics than DP
As it not possible to fit an example in the video now, here's one example that can help you understand better. Let's suppose we are solving for n = 8 dp[i] being number of ways to generate a sum of i dp[0] = 1 (base case) dp[1] = dp[0] = 1 dp[2] = dp[1] + dp[0] = 2 dp[3] = dp[2] + dp[1] + dp[0] = 4 dp[4] = dp[3] + dp[2] + dp[1] = 8 dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0] = 16 dp[6] = dp[5] + dp[4] + dp[3] + dp[2] + dp[1] + dp[0] = 32 dp[7] = dp[6] + dp[5] + dp[4] + dp[3] + dp[2] + dp[1] = 63 dp[8] = dp[7] + dp[6] + dp[5] + dp[4] + dp[3] + dp[2] = 125 Hope this helps.
The value of 'i' is different in all those 6 ways. You can get to k from k - 1, k - 2, k - 3, k - 4, k - 5, k - 6. So you add k - i, 6 times, each time with a different value of i.
We can consider that after this playlist. Btw, we will be teaching that in TLE Eliminators Level 4 which will be starting in December first week. You can check that out too if you're interested.
Great explanation ❤ please dont stop this series ❤❤❤i just had a doubt . I know basics of recursion...like i dont know advance topics like backtracking, subsequences etc...but i can understand basic recursion being used in the series ....can i still continue the series or should i learn them first
There is no pre-requisite for this playlist as such. You can learn the concepts along the way as well. Just try to grasp as much as you can. If you're stuck somewhere you can make a comment and we can provide you with the right guidance or resource to go forward.
Try iterative code. As explained by Priyansh, recursive codes are slower than iterative codes. Also, on CSES the time limit is very tight so generally recursive codes get a TLE.
Dp[i] = number of ways to get a sum of i Dp[0] = 0, because number of ways to get a sum of 0 is 1 way, that 1 way is in which you don't roll any dice. This is similar to how we write 0! = 1 because number of ways to arrange 0 items is 1, that 1 is way is to not do anything.
explanation was good but no offence, it would've been better if you had wrote the recursive soln first and then gone to the iterative one. Kind of hard to come up with a recursive soln by myself considering I've never studied dp before and this is a beginner playlist.
We believe you're watching this video with a bias that one must come up with a recursive solution first for every dp problem and then go to the iterative solution. The main aim of this playlist is to help you give up on that bias. The single most generic way to think about a DP problem is in terms of subproblems. Now for the code, if a state is dependent on some other states, you need to make sure that the states on which we depend are calculated first because only then we can calculate our current answer.
Hiey priyansh Bro it is Day02 here i go with my feedback can you also share you ipad / canvas notes i don't what it is.... and i can't recognized for 2nd code why we writing j
1. Sure, we will get the notes added in the description. 2. In the 2nd approach, dp[i] = number of ways to go from i to n. So, you are going higher from i by adding j to it. Now, you want to go from i to n and you're adding j for that. Clearly, if i + j > n, then you will never reach n, you will cross it. so that is i + j
@@TLE_Eliminators Okay Thanks now i get it the 2nd point .. I'll be Okay to watch again no issue for that it is normal feedback and if you also add some test case with dry run like you mantion in some one comments for n = 8 . but you don't explain it in video just add it in comments or description we will do by ourself it'll be helpful Thanks Again for checking comments ☺️
Going from 0 to 0, there is 1 way. That way is where you don't pick up any coin. It is similar to saying 0! = 1, number of ways to arrange 0 elements is 1.
![[CSES][Dynamic Programming] Dice Combinations](http://i.ytimg.com/vi/G6Et8daDTHU/mqdefault.jpg)
Watch this lecture if you find the concepts discussed in this video to be unknown: ua-cam.com/video/_OPJaU2Xz7o/v-deo.html. Basics of DP have been covered in this video.
Crystal Clear Explanation!! Understood very well
awesome lecture, loved it.
Very good explanation! Thank you.
Thanks Priyansh Bhaiya, I was able to solve this problem by own after watching first lecture but was unable to implement approach 2.🙂
Approach 2 is just the reverse of approach 1.
Approach 1:
state: dp[i] = number of ways to reach a sum of i
transition: dp[i] = sum(dp[i-1], dp[i-2]... dp[i-6])
base case: dp[0] = 1, as number of ways to generate 0 is just 1
final subproblem: dp[n] as we finally want to find the number of ways to get n
Approach 2:
state: dp[i] = number of ways to go from i to n
transition: dp[i] = sum(dp[i+1], dp[i+2]... dp[i+6])
base case: dp[n] = 1, as number of ways to go from n to n is just 1
final subproblem: dp[0] as we finally want to find the number of ways to go from 0 to n
What's the issue you faced in implementing?
@@TLE_Eliminators Because I was doing recursively and memoising . I was able to understand the first but second one took some time to understand.
Nice sir, would it be possible to create a playlist for another topic? It would be really helpful.
Let's finish this one off first and then we can plan more content.
We also have our upcoming TLE 9.0 course coming up in December 1st week that you can explore in case you're interested in other topics than DP
understood, very clear explanation :)
OG video!
Just wow❤
Can you please discuss the bonus problem i am not getting it perfect solution anywhere it will be a great help Priyansh
Nice explanation
great priyansh bhaiya
Try to start with a recursive solution then memo. And then tabulation ..
If you can give hint like how to do it recursively I have tried but confused.
We would suggest watching this video and you'll understand completely how to implement: ua-cam.com/video/_OPJaU2Xz7o/v-deo.html.
Recursive approach tried:
long long int num_of_ways(long long int n){
if(n
for (int i = n ; i >= 0; i--) {
for (int j = 1; j
pls reply
Awesome bro..
I would love to see the explanation with an example.
As it not possible to fit an example in the video now, here's one example that can help you understand better.
Let's suppose we are solving for n = 8
dp[i] being number of ways to generate a sum of i
dp[0] = 1 (base case)
dp[1] = dp[0] = 1
dp[2] = dp[1] + dp[0] = 2
dp[3] = dp[2] + dp[1] + dp[0] = 4
dp[4] = dp[3] + dp[2] + dp[1] = 8
dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0] = 16
dp[6] = dp[5] + dp[4] + dp[3] + dp[2] + dp[1] + dp[0] = 32
dp[7] = dp[6] + dp[5] + dp[4] + dp[3] + dp[2] + dp[1] = 63
dp[8] = dp[7] + dp[6] + dp[5] + dp[4] + dp[3] + dp[2] = 125
Hope this helps.
@@TLE_Eliminators Yes it helped me and I hope you add a example with explanation in upcoming videos.
why are we adding dp[k-i], 6 times to get dp[k] ??
The value of 'i' is different in all those 6 ways. You can get to k from k - 1, k - 2, k - 3, k - 4, k - 5, k - 6. So you add k - i, 6 times, each time with a different value of i.
Sir, could you please also share the slides for future reference. It will help us a lot if you provide a link for the same in description.
We are not going with slides. Priyansh writes all the stuff live while teaching.
@@TLE_Eliminators please share the live slide itself for future reference , if possible
Bro make small playlist of Digit dp as well , i could not found quality content for this topic on yt
We can consider that after this playlist. Btw, we will be teaching that in TLE Eliminators Level 4 which will be starting in December first week. You can check that out too if you're interested.
awesome
Is anyone solve the bonus problem (frog jump ii)?
I didn’t find any dp solution.
.
If anyone can, please help.
Getting tle in python although approach is same.
Please explain
I used dictionary
Great explanation ❤ please dont stop this series ❤❤❤i just had a doubt . I know basics of recursion...like i dont know advance topics like backtracking, subsequences etc...but i can understand basic recursion being used in the series ....can i still continue the series or should i learn them first
There is no pre-requisite for this playlist as such. You can learn the concepts along the way as well. Just try to grasp as much as you can. If you're stuck somewhere you can make a comment and we can provide you with the right guidance or resource to go forward.
@@TLE_Eliminators thank you
thanks sir
Understood
Nice
what is the one way to achieve sum of 0 ???
do not throw the dice.. that is the way
please can you explain Approach 1 ?
We would suggest watching the playlist in the series in order to understand everything. You can start from the first video to get started.
Recursive + memo in python giving TLE
Try iterative code. As explained by Priyansh, recursive codes are slower than iterative codes. Also, on CSES the time limit is very tight so generally recursive codes get a TLE.
store calculated values and then use them to calculate bigger value
Shouldn't the base case be Dp[0] = 0 bcoz we don't need to roll any dice.
Dp[i] = number of ways to get a sum of i
Dp[0] = 0, because number of ways to get a sum of 0 is 1 way, that 1 way is in which you don't roll any dice.
This is similar to how we write 0! = 1 because number of ways to arrange 0 items is 1, that 1 is way is to not do anything.
Can you please provide link to solve this question. Leet code or any other link
It is present in the description.
which theme are you using in sublime text
Brogrammer
@@TLE_Eliminators - which app is used for recording on the ipad and on mac laptop
@@Technology_Forum Goodnotes
❤
explanation was good but no offence, it would've been better if you had wrote the recursive soln first and then gone to the iterative one. Kind of hard to come up with a recursive soln by myself considering I've never studied dp before and this is a beginner playlist.
We believe you're watching this video with a bias that one must come up with a recursive solution first for every dp problem and then go to the iterative solution. The main aim of this playlist is to help you give up on that bias. The single most generic way to think about a DP problem is in terms of subproblems. Now for the code, if a state is dependent on some other states, you need to make sure that the states on which we depend are calculated first because only then we can calculate our current answer.
I liked , it feels like paid series but age jake quality mat gira dena please
don't worry, Priyansh never drops his quality irrespective of whether it is a paid course or a free playlist on UA-cam.
Is the given bonus problem either frog jump ii or frog jump? @@TLE_Eliminators
Hiey priyansh Bro it is Day02 here i go with my feedback can you also share you ipad / canvas notes i don't what it is.... and i can't recognized for 2nd code why we writing j
1. Sure, we will get the notes added in the description.
2. In the 2nd approach, dp[i] = number of ways to go from i to n. So, you are going higher from i by adding j to it. Now, you want to go from i to n and you're adding j for that. Clearly, if i + j > n, then you will never reach n, you will cross it. so that is i + j
@@TLE_Eliminators Okay Thanks now i get it the 2nd point .. I'll be Okay to watch again no issue for that it is normal feedback and if you also add some test case with dry run like you mantion in some one comments for n = 8 . but you don't explain it in video just add it in comments or description we will do by ourself it'll be helpful Thanks Again for checking comments ☺️
sir can u tell me what are the topics we need to concentrate more in dsa in order to improve in DSA problem solving
Linked List, BST, Stacks, Queues, DP, Graphs, Trees, String Algos and Tries
@@PriyanshAgarwal sir in string algos in which questions we need to concentrate more sir
#day2
not understood
I know that the solution is accepted but shouldn't ways to get 0 be 0
Going from 0 to 0, there is 1 way. That way is where you don't pick up any coin.
It is similar to saying 0! = 1, number of ways to arrange 0 elements is 1.
hi bro i think this is also working
vll dp(1000001,-1);
void solve()
{
ll n;cin>>n;
cout