Climbing Stairs | 3 Approaches | Leetcode 70
Вставка
- Опубліковано 25 сер 2024
- This is the 7th Video on our Dynamic Programming (DP) Playlist.
In this video we will try to solve a very good, interesting and famous Problem "Climbing Stairs".
We will try to understand how we come up with the DP approach. The intuition behind it. And see time and space complexity.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Climbing Stairs
Company Tags : Google, Amazon, OYO Rooms, Microsoft, Adobe, Flipkart, Siemens(MentorGraphics)
My solutions on Github : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
Guys this Qn was also asked by Google.
Time Complexity :
1) Recursion : O(2^n) - We have 2 possibilities for every stair.
2) Memoization : O(n) - We are not visiting already solved subproblems
3) Bottom UP : O(n) as we are iterating only once from i = 3 to i = n
I seriously watched this video twice. You are so clear with your words man.
The way you explain makes it so evident that you have amazing clarity. Thanks a lot man.
You have become an inspiration of my whole group in college.
i already did the Q's but came here to watch your intuition
can you please make a dynamic programming playlist...your explanation style is diff and really really good
Thanks a lot Mohit.
Yes, i am taking out time to work on playlists. Time crunch causing delay.
Will soon be out.
Thanks again for watching ❤️❤️❤️
your explaining approach is too good brother !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Thank you so much ❤️❤️❤️
i have started my interview cracking journey by taking your channel as my full and proper guide.Hoping for the best outcome🙂
❤️❤️❤️
Your way of explaining things from multiple perspectives deserves a lot of appreciation. Good work, keep it up :)
Thank you so much Aakash ❤️❤️🙏🙏
This means a lot to me. You made my day 🙏🙏
Learned so much from this video😊
This is gold 🔥
Potd done .
fibonacci approach is 👌
Amazing
Thanks a lot Manish ❤️❤️❤️
thanks!
Glad I could help ❤️
sabko memoization nhi aata 🥺🥺 but abh aa gya
Thanks a lot Yash.
So glad to hear that ❤️❤️❤️
Same
tysm sir
Superb explanation.
Best explanation literally 🔥
/*
//APPROACH 1: TLE WITHOUT MEMOISATION:: going from 0 steps to n steps
class Solution {
public:
int dp[46];
int findWays(int &n, int step){
int ways = 0;
if (step == n){
return 1;
}
else if (step > n){
return 0;
}
if (dp[step] != -1)
return dp[step];
ways += findWays(n, step+1);
ways += findWays(n, step+2);
return dp[step] = ways;
}
int climbStairs(int n) {
memset(dp,-1,sizeof(dp));
int currentStep = 0;
return findWays(n,currentStep);
}
//same approach (coming back from nth step to 0th step)
class Solution {
public:
int dp[46];
int findWays(int step){
if (step == 0){
return 1;
}
else if (step < 0){
return 0;
}
if (dp[step] != -1)
return dp[step];
return dp[step] = findWays(step-1) + findWays(step-2);
}
int climbStairs(int n) {
memset(dp,-1,sizeof(dp));
return findWays(n);
}
//approach 2: BOTTOM UP DP: TABULATION
int climbStairs(int n) {
vector dp(n+1, 0);
dp[0] = dp[1] = 1;
for(int i = 2; i
Thanks a lot bhaiya ❤❤
Most welcome ❤️🙏
Bhaiya name pata chal gya hai apka "Mazhar Immam Khan"🙂
The best tutor
❤
You r great
🙏🙏
Thanks ❤
You're welcome 😊
Java Implementation:
Rec + Memo
class Solution {
private int solve(int n, int[] t) {
if(n
Great video explaination I love your content
Just a minor suggestion at 28:20 tem_b lene ke bajaye
a=b;
b=c;
bhi ar sakte hai
koi badi galti nahi hai bas space bacha raha hu :P :)
❤️❤️🙏
Really thankyou bhaiya u are just amazing I haven't studied dp yet but this is magic of your teaching that I
Got to know something about dp,memoization and this itself is big for me
Also one request bhaiya when u have sufficient tym please please please start dp from very scratch level till advance level as it will be blessing for us
And also bhaiya the memoization code is not working as for n=45 it is showing TLE in my case but in your case it is getting pass also try to figure out my mistake and even pasted the same code of yours but in both cases I am getting TLE don't know why bhaiya
Thanks a lot Uday.
Sure i will keep that in mind
Can you share your code ?
@@codestorywithMIK pta nhi ab kaise kaam kr raha haa ho skta maine hi kuch galti ki hogi jo mai dekh nhi paya isiliye pass nhi ho raha tha sorry haa bhaiya
Great
No worries 😃
can you share me ppt/slide of dp. playlist.( your intuition of a problem is best)
Java solution:
class Solution {
private int solve(int n,int[] dp){
if(n
sir this code give runtime error for n==38 but when i comment dp.clear() it will submit why? please reply and bhaiya the way you explain is soo good
vectordp;
int solve(int n){
if(n==0 || n==1) return 1;
if(dp[n]!=-1) return dp[n];
return (dp[n]=climbStairs(n-1)+climbStairs(n-2));
}
int climbStairs(int n) {
dp.clear();
dp.resize(46,-1);
return solve(n);
}
You should call solve function recursively but instead you are calling climbStairs. Plz re-check the return statement of solve function.
LEGEND
Sir your explanation so easy and I can fully understand the sol and question.
But before watching video I think of many caseand think the problem as hard for my level but actually these problems are not so hard.
How to come up woth logic my self
Hi Dania, thank you for your kind words.
And regarding the logic, it’s the beginning , just keep solving like this everyday, with time it builds on its own.
The only thing you have to do is be consistent and never memorise a solution. Always understand the intuition.
Slowly it will start coming to you too
bhaiya maine yeh code likha jiske liye voh error throw krrha hai?
error " : Char 18: error: expected parameter declarator
vectort(46, -1);"
mycode
vector t(46, -1); // Initialize a vector of size 46 with all elements set to -1
int solve(int n) {
if (n < 0) return 0;
if (n == 0) return 1;
int val = t[n];
if (val != -1) return val;
int oneStep = solve(n - 1);
int twoStep = solve(n - 2);
return t[n] = oneStep + twoStep;
}
int climbStairs(int n) {
return solve(n);
}
Hey, actually In C++, member variables with non-static const integral types can be initialized in the class declaration, but you cannot use parentheses for the initialization.
In simple language, In C++, when you declare a member variable in a class, you can't directly initialize it with parentheses like you did for the vector t. Instead, you need to initialize it in the class constructor or do like I did below :
So ,you should do like this below :
class Solution {
public:
vector t;
int solve(int n){
if(n < 0)
return 0;
if(n == 0)
return 1;
if(t[n] != -1)
return t[n];
int a = solve(n-1);
int b = solve(n-2);
return t[n] = a+b;
}
int climbStairs(int n) {
t = vector(46, -1);
return solve(n);
}
};
I have a question. When we are at step 2, why can't we find how many steps are required if we came one step down, which is step 1, and if we came 2 steps down which is 0. And as we know from step 1 it's one way and from step 0 it's zero way, so total at step 2 could be 1 + 0 = 1 way. Why does this contradict the fact that we have 2 ways for step 2. Not sure how to understand this part.
reach++
Tysm ❤️❤️❤️
sir i have a small doubt as follows:
why does this code give runtime error?
class Solution
{
public:
int climbStairs(int n)
{
vector dp(n + 1, -1);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i
This happens because , if you notice in the input constraints, it’s mentioned that
1
@@codestorywithMIK thanks a lot sirr this thing was bugging me for almost a week, faced similar runtime error in many questions
bhai ye old front view kaise kiya leetcode mai ?
Go to any question description page, click your userpic, you can switch to the old version from the drop down menu “Revert To Old Version”
@@codestorywithMIK thanks bhai soon your videos will reach 1K views for every video
Thanks a lot ❤️
❤