Points to remember: Step1. Identify a DP Problem. Step2. To solve the problem after identification. 1. Try to represent the given problem in terms of index. 2. Do all possible operations on that index according to the problem statement. 3. To count all possible ways - sum of all stuff. To find minimum/maximum - Take Minimum/maximum of all stuff. Understood 🔥🔥🔥
Great work Striver. Just couple of observations since f(n) denotes no of ways to reach nth stair from step 0. It implies f(0) should be 0(you don't have to move at all, you are already at your destination), f(1)=1(because only one step of single jump needed) and f(2) = 2 because in this case either two times a 1-step can be taken or a single 2-step works. So closely this pattern doesn't resemble fibonacci till index 2, because f(2) is not a sum of f(1) and f(0), rather they are adding upto 1. So my logic would be: // JS Snippet const climbStairs = function(n) { const recursion = (i) => { if(i
Firstly I thought that at f(0) he can't move and over there return 1 indicates that even not moving can be considered as a way but it will be same for entire problem and make it unsolvable but it isn't so you have cleared thank you
1. Try to represent any problems in terms of index 2. Do all possible stuffs on that index, according to the problem statement 3. Sum of all stuffs ->count all the ways , min(of all stuffs) -> Find min
I understood this as : to reach the nth stair, you find out the ways to reach the (n-1)th stair (from where you take 1 step to reach nth stair) and the ways to reach the (n-2)th stair (from where you take 2 steps to reach the nth stair), and sum them to get total no. of ways. Is my understanding correct?
points to remember any problem should be broken down to a recursive function. 1. try indexing 2.try writing all possibilities using indexes 3.for finding min /max => count the no. of ways(sum of all f(n))=>min/max(all posssible f(n))
Understood! earlier was doing it in another way, but today i got a new way of thinking i.e. if we are on nth idx then we have jumped from n-1th and n-2th 🙃
@@ManishKumar-qx1kh I am not able to focus most of the time on actual content due to the face. In Aditya Verma video I like the fully content screen. And about free content, yes we get the content as free and do you think someone in this world will work to provide such valuable content without getting paid. I guess some indirect money must motivating them to provide such incredible content.
@@VivekJaviya bro iam also preparing in the same pattern nd I'm currently studying mca 1st year. Iam looking for ppo's in mncs like Goldmansachs, Amazon, uber etc...could you plz say ur linkedin id?
Hi striver, if you're reading this then I'd request you to put this video in the shortened version of this playlist as well since here you're teaching how to encounter problems related to 1D array which is necessary to understand to be able to solve 1D problems on DP.
Do I just need to solve these questions first before attempting anything similar on leetcode or do I need to do both leetcode and your problems both on parallel....btw you are the best teacher I ever learned from...keep on making these videos man...and education would become completely free soon!
Thanks for the explanation and whole series!. Shouldn't base case be if(index === 0) return 0 ?. If this is right, then when n=3, we will have only 2 possible ways to reach step 3 which is incorrect ?.
We are not counting the number of steps but the number of ways. So as soon as the function hits 0, we can say that we have found a new way and hence return 1.
I am unable to understand why we need 1 to jump to same stair that is from 0->0 (base case)? According to me it should be zero. Correct me if I am wrong.
I too didn't understood in the beginning but after sometime I figured out that = see you are coming from n to reach 0 which means there is way from n to our destination '0' so you return 1 saying that there is a possible way from n to reach 0 so it is returning true. You should not think like from 0 to 0 there is no way then why i am returning 1. You have think from the given "n' perspective. because 0 is the last index to get on so if we get to the last index we found out a way from n. So when we reach to 0 index we are saying to n that " hello n there is a possible path from u".
I'm ur new subscribers. Thank u for all the efforts and please continue to do so. Ur lectures are great. Please explain me the base case : Why return 1 ?
you can think (n == 0) as you have ultimately reached to your destination i.e. at the nth step and no need to take any more step and thus you can conclude that you have found one of the way to reach the nth stair and hence return 1 indicating that hey I have found one of the possible way to reach the target and you can actually increment the total count of possible ways to reach the nth stair I hope it helps
Python Most optimized solution => def climbStairs(self, n: int) -> int: prev = 1 prev2 = 1 res = 1 for x in range(2,n+1): res = prev + prev2 prev2 = prev prev = res return res
Bhaiya I am currently learning c++ by this month I will complete all fundamentals of c++ Please bhaiya can you suggest me where to start DSA as a beginner ????? Please bhaiya reply Love from Guwahati ❤️
remember as if for standing in the same place there is one way , logically speaking there is no way , but if we are considering the problem here it will be 1
You are right. It should be 0 as we have already reached the destination and don't need to move any further. You can write separate base case like if (index
@@rohalkurup1350 but is it kind of confusing ?. because at step 1, yes there is one way to reach step 0, but at step 0, there is no way to reach as it is already reached. bit confusing this part is. :-(
UNDERSTOOD. But there is a small issue in the base case, n = 0 doesn't make any sense according to the problem, so we need to set the base case as n = 1 and n=2. Rest everything is understood. Thanks for the videos
//memoization #include #include using namespace std; int frog(int n,vector &dp){ //base case explanation // If n is 0, the function returns 1. This is because if the frog is already at position 0, then it doesn't need to make any more jumps to reach position 0, so there is only 1 way to do so. //If n is 1, the function returns 1 as well. This is because if the frog is at position 1, it can only make one jump of 1 step to reach position 0, so there is only 1 way to do so. if(n==0){ return 1; } if(n==1){ return 1; } // condition for dp if(dp[n]==-1){ int left=frog(n-1,dp); int right=frog(n-2,dp); return dp[n]=left + right; } else{ return dp[n]; } } int main(){ int n; cin>>n; vector dp(n+1,-1); cout
bhai, if the frog is already at position 0, then it doesn't need to make any more jumps to reach position 0, SO IF oesn't need to make any more jumps to reach position 0, THEN WHY DOES HE NEED TO JUMP IF HE HAS ALREADY ARRIVED THERE? I'M V CONFUSED ABOUT THIS
// we will make solution from top to bottom here class Solution { public: int recur(vector &dp,int n,int i){ // base case , dp[i] != -1 case , do something if(i == 0) return 1; if(i == 1) return 1; if(dp[i]!=-1) return dp[i]; return dp[i] = recur(dp,n,i-1) + recur(dp,n,i-2); } int climbStairs(int n) { vector dp(n+1,-1); return recur(dp,n,n); } }; top to bottom dp solution if someone wants
From step N-1 there is only 1 way to reach Nth step i.e. a 1-step jump. But from step N-2 there are 2 ways to reach step N, 2 1-step Jump and 1 2-step jump. So the recursion shall be Sol(N) = [Sol(N-1)*1] + [Sol(N-2)*2]; because for each Sol(N-2) we have 2 ways to reach Sol(N).
Understood!! Points covered: Step1. Identify a DP Problem. Step2. To solve the problem after identification. 1. Try to represent the given problem in terms of index. 2. Do all possible operations on that index according to the problem statement.
Hi Striver @takeUforward, one question here, As you said previously if we need to find all possible ways then we try recursion and backtracking, Here again we are saying same thing. So does it mean dp is just the optimized way of solving backtracking problems with time and space both optimized?
can also solve using this way int helper(int i,int n,vector&dp){ if(i==n)return 1; if(i>n)return 0; if(dp[i]!=-1)return dp[i]; return dp[i]=helper(i+1,n,dp)+helper(i+2,n,dp);
} int climbStairs(int n) { vectordp(n+1,-1); return helper(0,n,dp); }
trust me striver. after watching your videos and solving many questions i am able to think how to solve any problem and only thing lagging behind that its not the complete solution my made up solutions always have some edge case which you always solve it
You say consistency !!! I hear Striver !!!! 😊😊😊 Man you are too good !!!!
Points to remember:
Step1. Identify a DP Problem.
Step2. To solve the problem after identification.
1. Try to represent the given problem in terms of index.
2. Do all possible operations on that index according to the problem statement.
3. To count all possible ways - sum of all stuff.
To find minimum/maximum - Take Minimum/maximum of all stuff.
Understood 🔥🔥🔥
These steps will work well on leetcode/GFG but not on codeforces
For CP, you need to watch priyansh video
I finished my engineering and now I m working , came back to listen to the song that gets played for few seconds in last . Good old days.
yeahh I too love to listen to it...
Great work Striver. Just couple of observations since f(n) denotes no of ways to reach nth stair from step 0. It implies f(0) should be 0(you don't have to move at all, you are already at your destination), f(1)=1(because only one step of single jump needed) and f(2) = 2 because in this case either two times a 1-step can be taken or a single 2-step works. So closely this pattern doesn't resemble fibonacci till index 2, because f(2) is not a sum of f(1) and f(0), rather they are adding upto 1. So my logic would be:
// JS Snippet
const climbStairs = function(n) {
const recursion = (i) => {
if(i
Was thinking the same!!
Thank you Nikhil. You explained it very easily. So I wrote it this way:
//JS Snippet
function numOfStairs(n) {
if (n
Firstly I thought that at f(0) he can't move and over there return 1 indicates that even not moving can be considered as a way but it will be same for entire problem and make it unsolvable but it isn't so you have cleared thank you
I was thinking the same.. that why is there 1 ways to reach stair 0?
Your code will fail for 3
1. Try to represent any problems in terms of index
2. Do all possible stuffs on that index, according to the problem statement
3. Sum of all stuffs ->count all the ways , min(of all stuffs) -> Find min
Finally after 7 month because of you bhaiya got to know the intuition behind aolving a DP problem and the patterns too.....fully understood
Yess
I understood this as : to reach the nth stair, you find out the ways to reach the (n-1)th stair (from where you take 1 step to reach nth stair) and the ways to reach the (n-2)th stair (from where you take 2 steps to reach the nth stair), and sum them to get total no. of ways. Is my understanding correct?
Absolutely correct
points to remember
any problem should be broken down to a recursive function.
1. try indexing
2.try writing all possibilities using indexes
3.for finding min /max => count the no. of ways(sum of all f(n))=>min/max(all posssible f(n))
Understood! earlier was doing it in another way, but today i got a new way of thinking i.e. if we are on nth idx then we have jumped from n-1th and n-2th 🙃
understood
solved the problem on my own just after reading the question thanks to your recursion playlist and 1st video on dp
Understood! Loved how you simplified the recurrence relations thing!
Just a suggestion you can cover whole screen by the black board, just a small rectangule for your face at left or right bottom
The iPad screen reso is small. So if I elongate it to the whole screen, it stretches and the colors go off.
Face is not required.
Padhai kar lo, face rhe na rhe usse kya h. 😂
@@rabindrakumar949 why r u focusing on the face, just get the knowledge he is sharing for free.
@@ManishKumar-qx1kh I am not able to focus most of the time on actual content due to the face. In Aditya Verma video I like the fully content screen. And about free content, yes we get the content as free and do you think someone in this world will work to provide such valuable content without getting paid. I guess some indirect money must motivating them to provide such incredible content.
Bestest stuff of all the cases of tutorials on youtube
Understood, Thank You So Much for this wonderful video...🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Leetcode daily problem + Codechef daily problem + GFG daily Problem + Striver Daily dp problem = :)
=Google
So, ur planning to become SDE in Meta 🤙
@@kingmaker9082 Meta to nhi but USA ke startup or MNC se offer to mil gaye upar ki chijo se!
@@VivekJaviya bro iam also preparing in the same pattern nd I'm currently studying mca 1st year. Iam looking for ppo's in mncs like Goldmansachs, Amazon, uber etc...could you plz say ur linkedin id?
Are you saying practicing every day or are you talking about the problem which is given everyday on LeetCode and GfG?
Hi striver, if you're reading this then I'd request you to put this video in the shortened version of this playlist as well since here you're teaching how to encounter problems related to 1D array which is necessary to understand to be able to solve 1D problems on DP.
Day - 1 : understood the three points clearly
Understood! I done this question myself thanks a lot to u for this amazing series
class Solution {
public int climbStairs(int n) {
int prev2 = 1;
int prev1 = 1;
for(int i =2;i
3/57 done!!! Understood!
I struggled hard to get its recursive bit u made it so much easy
Do I just need to solve these questions first before attempting anything similar on leetcode or do I need to do both leetcode and your problems both on parallel....btw you are the best teacher I ever learned from...keep on making these videos man...and education would become completely free soon!
Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
if logic is magic then you are a great magician appreciate it sir ❤️
Thanks for the explanation and whole series!. Shouldn't base case be if(index === 0) return 0 ?. If this is right, then when n=3, we will have only 2 possible ways to reach step 3 which is incorrect ?.
We are not counting the number of steps but the number of ways. So as soon as the function hits 0, we can say that we have found a new way and hence return 1.
int countDistinctWays(int nStairs) {
//DP Tabulation solution
int mod = 1000000007;
vectorDP(nStairs+2, -1);
//Initial Steps
DP[0] = 1;
DP[1] = 1;
for(int i= 2; i
Why you took nstairs+ 2 istead off nstairs +1?
@@shreyanshgupta6163it should be n+1
Thanks for explaining in English.. love from Tamilnadu 😎
int ways(int i,int n, vector&dp){
if(dp[i]!=-1){
return dp[i];
}
if(i==n){
return 1;
}
if(i>n){
return 0;
}
return dp[i]=ways(i+1,n,dp)+ways(i+2,n,dp);
}
Why this gives heap buffer exceeded and why we go from n to 0
when we go can go from 0 to n
Amazing Lectures ,learnt a lot .Great initiative.
I am unable to understand why we need 1 to jump to same stair that is from 0->0 (base case)? According to me it should be zero. Correct me if I am wrong.
I too didn't understood in the beginning but after sometime I figured out that = see you are coming from n to reach 0 which means there is way from n to our destination '0' so you return 1 saying that there is a possible way from n to reach 0 so it is returning true. You should not think like from 0 to 0 there is no way then why i am returning 1. You have think from the given "n' perspective. because 0 is the last index to get on so if we get to the last index we found out a way from n. So when we reach to 0 index we are saying to n that " hello n there is a possible path from u".
@@sandeepdeepu5052 thank u
@@kaushikmahanta6463 felt happy that you understood my explanation.
UNDERSTOOD! Thank you striver!!
Represent the problem in index format
Do all possible operations on the index
do count or find min/max
Understood!
I'm ur new subscribers.
Thank u for all the efforts and please continue to do so.
Ur lectures are great.
Please explain me the base case :
Why return 1 ?
Bcoz there is only one way to reach step 1 from step 0
you can think (n == 0) as you have ultimately reached to your destination i.e. at the nth step and no need to take any more step and thus you can conclude that you have found one of the way to reach the nth stair and hence return 1 indicating that hey I have found one of the possible way to reach the target and you can actually increment the total count of possible ways to reach the nth stair
I hope it helps
Learning to be consistent from you sir.. UNDERSTOOD
Python Most optimized solution =>
def climbStairs(self, n: int) -> int:
prev = 1
prev2 = 1
res = 1
for x in range(2,n+1):
res = prev + prev2
prev2 = prev
prev = res
return res
yeah but the concept is on dp ...
Tabulated solution:
function f(n){
if(n
Great Explaination in building the recursion. Thanks
More power to you striver... "UNDERSTOOD"
Here's the c++ code which I submitted (For reference):
int f(int n, vector &dp){
if(n
one small mistake ,for idx==1, return 1 aayega instead of 0, nicee explanation sir❤❤
he mentioned in video ,u missed
At 7:25 , it will be return 0 when (ind==0)
no it will be 1
yaara ne
The first thought It came to my mind was permutation and approached like permutation with repetition, but it gave timeout for test cases after n=30.
Understood! Thank you very much, sir.
Bhaiya I am currently learning c++ by this month I will complete all fundamentals of c++
Please bhaiya can you suggest me where to start DSA as a beginner ?????
Please bhaiya reply
Love from Guwahati ❤️
For DSA in cpp check out dsa playlist from simple snippet!
Abdul bari
@@AbhishekSingh-kt8fiso means after c++ i can start with simple snippet???
@@harshitparashar for beginners will it be good???
@@karanjitsinghrandhawa445 yup
understood! but one confusion... shouldn't it be "if(ind == 0) return 0; " as we are left with no way to reach to the end when ind equals 0 !
remember as if for standing in the same place there is one way , logically speaking there is no way , but if we are considering the problem here it will be 1
@@rohalkurup1350 how 1?
You are right. It should be 0 as we have already reached the destination and don't need to move any further. You can write separate base case like if (index
@@rohalkurup1350 but is it kind of confusing ?. because at step 1, yes there is one way to reach step 0, but at step 0, there is no way to reach as it is already reached. bit confusing this part is. :-(
Damn , this is what tier 3 college should teach in DSA's classess!
UNDERSTOOD. But there is a small issue in the base case, n = 0 doesn't make any sense according to the problem, so we need to set the base case as n = 1 and n=2. Rest everything is understood. Thanks for the videos
//memoization
#include
#include
using namespace std;
int frog(int n,vector &dp){
//base case explanation
// If n is 0, the function returns 1. This is because if the frog is already at position 0, then it doesn't need to make any more jumps to reach position 0, so there is only 1 way to do so.
//If n is 1, the function returns 1 as well. This is because if the frog is at position 1, it can only make one jump of 1 step to reach position 0, so there is only 1 way to do so.
if(n==0){
return 1;
}
if(n==1){
return 1;
}
// condition for dp
if(dp[n]==-1){
int left=frog(n-1,dp);
int right=frog(n-2,dp);
return dp[n]=left + right;
}
else{
return dp[n];
}
}
int main(){
int n;
cin>>n;
vector dp(n+1,-1);
cout
bhai, if the frog is already at position 0, then it doesn't need to make any more jumps to reach position 0,
SO IF oesn't need to make any more jumps to reach position 0, THEN WHY DOES HE NEED TO JUMP IF HE HAS ALREADY ARRIVED THERE? I'M V CONFUSED ABOUT THIS
thanks bro, understood..
Not getting feeling of Solution....
but understood the shortcut very well...
thank you😀
Awsome explanation, memorize fibonacci solution in JS:
const m = {};
function fib(i) {
if (i
// we will make solution from top to bottom here
class Solution {
public:
int recur(vector &dp,int n,int i){
// base case , dp[i] != -1 case , do something
if(i == 0) return 1;
if(i == 1) return 1;
if(dp[i]!=-1) return dp[i];
return dp[i] = recur(dp,n,i-1) + recur(dp,n,i-2);
}
int climbStairs(int n) {
vector dp(n+1,-1);
return recur(dp,n,n);
}
};
top to bottom dp solution if someone wants
From step N-1 there is only 1 way to reach Nth step i.e. a 1-step jump. But from step N-2 there are 2 ways to reach step N, 2 1-step Jump and 1 2-step jump. So the recursion shall be Sol(N) = [Sol(N-1)*1] + [Sol(N-2)*2]; because for each Sol(N-2) we have 2 ways to reach Sol(N).
Liked the video even before starting it..Obviously its made by Striver ,it had to be great❤
isn't when index == 1, it should return 1 instead of 0.
Understood!
Mark for revision!
dp Solution :
static int fun(int n, int [] dp){
if(n==0){
return 1;
}
if(n0){
return dp[n];
}
int n1 = fun(n-1,dp);
int n2 = fun(n-2,dp);
int ans = n1+n2;
dp[n]=ans;
return ans;
}
It wont work for 1e18 test cases..
This is your only video till now that i didnt understood .
Kudos to your effort striver ❣
NICE SUPER EXCELLENT MOTIVATED
Thank you sir
Understood
Solution for Climbing Stairs:
#include
#include
using namespace std;
// recursive
// Time Complexity: O(2^N)
// Space Complexity: O(N) - stack space
int totalWays(int num) {
if(num == 0) return 1;
int step1 = totalWays(num-1);
int step2 = 0;
if(num-2 >= 0) {
step2 = totalWays(num-2);
}
return step1 + step2;
}
// memoization
// Time Complexity: O(N)
// Space Complexity: O(N) + O(N) - stack space
int helper(int num, vector& dp) {
if(num == 0) return 1;
if(dp[num] != -1) return dp[num];
int step1 = helper(num-1, dp);
int step2 = 0;
if(num-2 >= 0) {
step2 = helper(num-2, dp);
}
return dp[num] = step1 + step2;
}
int totalWays(int num) {
vector dp(num+1, -1);
return helper(num, dp);
}
// Tabulation
// Time Complexity: O(N)
// Space Complexity: O(N)
int totalWays(int num) {
vector dp(num+1, 0);
dp[0] = 1;
dp[1] = 1;
for(int i=2;i= 0) {
step2 = dp[i-2];
}
dp[i] = step1 + step2;
}
return dp[num];
}
// space optimization
// Time Complexity: O(N)
// Space Complexity: O(1)
int totalWays(int num) {
if(num == 0 || num == 1) return 1;
int prev = 1, secondPrev = 1;
for(int i=2;i
understod.thanks striver bhaiya
❤
Now I would believe in myself that I will be selected as A SDE in Amazon soon. Bhaiya with ur support & help.
did it myself feels soo godd hehe
Understood...Completed 2/56
Understood!!
Points covered:
Step1. Identify a DP Problem.
Step2. To solve the problem after identification.
1. Try to represent the given problem in terms of index.
2. Do all possible operations on that index according to the problem statement.
nderstood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
"UnderStood" Got it.
Understood the three points
Should'nt the base case be " if(ind==0) return 0 ". Correct me if I'm wrong.
Same doubt if u got answer tell me
"UNDERSTOOD!!"
when n==0, why did we return 1 ?
we should have return 0 because there is no staircase present so 0 steps will be required to climb it.
Hi Striver @takeUforward, one question here, As you said previously if we need to find all possible ways then we try recursion and backtracking, Here again we are saying same thing. So does it mean dp is just the optimized way of solving backtracking problems with time and space both optimized?
Understood striver
Awesome explanation!!
Understood sir 🔥💯
Now all CS student can do DP without any fear...
raj bhaiya "understood"
Thanks for the Video!
Understood
2/56
Hub gariboke DEVTA ho tum❤😅
This is so simple. Thank you Understood.
Amazing explanation 🔥🔥🔥
Understood !!! really awesome explaination........
can also solve using this way
int helper(int i,int n,vector&dp){
if(i==n)return 1;
if(i>n)return 0;
if(dp[i]!=-1)return dp[i];
return dp[i]=helper(i+1,n,dp)+helper(i+2,n,dp);
}
int climbStairs(int n) {
vectordp(n+1,-1);
return helper(0,n,dp);
}
Understood thanks striver❤
Understude Easily Nice Explanation
Understood Bhaiya
Jai Hind
understood heart felt thank you
Understood 🔥🔥🔥
Thanks for Your teachings
Awesome explanation👏
#define N 1000000007
vector dp(100000,-1);
int countDistinctWays(int nStairs) {
if(nStairs==0||nStairs==1)
return 1;
if(dp[nStairs]!=-1)
return dp[nStairs];
int left=countDistinctWays(nStairs-1);
int right=countDistinctWays(nStairs-2);
return dp[nStairs]=(left+right)%N;
}
Understood bhaiya! 🔥
UNDERSTOOD 🔥🔥
Understood.
Step 1: Write the problems in term of index.
Step 2: Do all possible operation on that index.
Step 3: Total ways: +1
max, min: find it.
Understood three points ❤
trust me striver. after watching your videos and solving many questions i am able to think how to solve any problem and only thing lagging behind that its not the complete solution
my made up solutions always have some edge case which you always solve it
understood 🙂
Kudos to your effort striver ❣️
bhayia your way of teaching is amazing.one thing i want to ask you that from where did you learned all these.
i love thi dp series