Climbing Stairs with Minimum Moves | Dynamic Programming Problem Explained
Vložit
- čas přidán 28. 07. 2020
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the solution of the Climb Stair in Minimum Moves problem where we are required to move from the ground level to the highest level with variable jumps and minimum move. In this problem,
1. You are given a number n, representing the number of stairs in a staircase.
2. You are on the 0th step and are required to climb to the top.
3. You are given n numbers, where ith element's value represents - till how far from the step you could jump to in a single move. You can of course jump fewer number of steps in the move.
4. You are required to print the number of minimum moves in which you can reach the top of staircase.
Note - If there is no path through the staircase print null.
#dp #dynamicprogramming #climbstairs
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
This playlist on DP deserves more views than any other Dp video on YT!! Loved your teaching. I wish I could get a teacher like u.
Thanks buddy!
It's all bcz of the love and respect which I get from you people which keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
Sir aap insaan ho yaa bhagwaan!!!
Literally u r great sir...
Just loved ur teaching... everything becomes crystal clear ....
This man makes logic easy 🔥
Video is end, wait wait pause it,
i'll have to like this video first
My mind always says to me after watching each and every of your videos.
Thanks for sharing
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities
Tabulation ke 3 niyam.....aur DP khatam...Awesome Explaination.
Actually, we don't need Integer[]. We can get the desired solution with primitive int[]. Memoized and simplified tabulation approach: public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i arr.length || arr[curr] == 0){
return Integer.MAX_VALUE - 1;
}
if(dp[curr] != 0){
return dp[curr];
}
int minWays = Integer.MAX_VALUE - 1;
for(int i=1; i=0; i--){
int jumps = arr[i];
int min = Integer.MAX_VALUE - 1;
for(int j=1; j
What resources are you referring to learn DP?
Great sir 👌
Thanks sir for the beutiful explaination
Memes within the content are just 🔥🔥🔥
There is a reason why there are no dislikes here , great explanation sir :)
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
@@Pepcoding sir pichle saal hi de diye the 5 star agar pandemic nahi hota to mein live padh rha hota 😂
Sir your recursion playlist was by far the best .Hope you will complete the DP one also :-)
Ofcourse we will. Have recorded 4 questions since morning, will come soon.
VERY NICE EXPLANATION SIR
I WERE LATE BY 1YR
Hi Sumeet sir! Love your videos, I've been going through all of your playlists on DSA, and you make it so easy! I just have one feedback, I think you should also mention the complexities of your solutions, since that's asked in almost every DSA interviews.
Surely we will focus on this. Thanks for your valuable feedback, For best experience visit on nados.pepcoding.com
best .. mazza aagya
Loved your teaching style, best channel , editing videos to make some fun really appreciate your efforts 😊
yahi to chaie
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
For clearing your doubts, you can join our community on telegram
t.me/pepcoding
@@Pepcoding Done 🥳🙏
Amazing sir
Keep watching
Sumeet Sir, I Am Continually Learning From Your Java Foundation Very Seriously, In Future Sir, I Eagerly Want To Join Pepcoding In FUTURE.
I Enrolled In Other Institute Then I Came To Know About PepCoding.
I Want To Get Connected To PepCoding.
Always welcome. You can contact us on 01140194461
amazing explanation sir :)
Glad you liked it!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
samajh mein aaya sir .
Keep learning and keep growing!
7:11 to understand it, find the min of (number of jumps after your jump) + 1.
Here, from 9, Min of(0, out_of_index) +1 = 1
why is it +1 ? can anyone explain
@@sauravdas7591 you have three step, source, middle, destination.
From middle to destination, min no of moves calculating by Solving min().
Now from source to middle, you can go with 1 step.
So total step required to go destination from source= 1+ intermediate steps.
See the diagram you will cleared.
clap for this but plzz solve this using recursion too
BEHTEREEN DP LIST 😍❤
Sumeet sir op!..waiting for offline classes
Thank you keep motivating, keep learning and keep loving Pepcoding😊
I understood this problem, thanks so much Sir, but abhi pichhle wale questions se confusion hone lagi hai. Kya karna chahiye ?
Sir, does this mean Integer takes more space than int?
please explain O(n) solution.
i understood this algorithm at 2nd index 😂
+1
will this code will work if last element is 0 of array...?
Hello sir...
This code is not working for input N=10
[2,3,1,1,2,4,2,0,1,1]. Please
right ans is 4 but compiled ans is 4.Please look into this
Again tq
So Nice of you keep motivating, keep learning and keep loving Pepcoding😊
int ka array nahi bana sakte..condition m if(i+j! = 0) kar dege
Sir hamne isme Integer.MAX_VALUE kyu use kiya hai ?
U r god😭🙏
Hello sir,
for this input
2 3 1 1 4
our DP solution is giving answer as 3
but actual answer is 2 . ( 2->3->4). 2 jumps
Kaise hoga bro sahi
bhai 6 stairs hain 0,1,2,3,4,5 aur last wali stair(5th wali) par koi jump value nahi rehati, ab try kar lena 3:00 se method follow karke answer aa jayega 3
n-1 of dp will also be initialized with 0 and outer loop will start from n-2. all test cases will be passed
SIr your explanation is the best ,but this code is not working fine
Op❤️
Hope you like the video.
For better experience and well organised content sign up on nados.io
And for being updated follow us on Instagram instagram.com/pepcoding/
Sir ye bataye ki koi agar first time DP kar raha ho aur saari video ke solution code nahi kar paa raha par question ko think kar raha and diagrams bhi execute ho rahe phir code implementation ke liye kya kare?
beta, maan lijie ki 200 ke 200 question ke bhi video dekh liye. Aur ab ye sare aa gae. To mai aapko ye bta sakta hun ki ache se dekhe honge aur dekh ke submit kiye honge to aap DP mei kabhi maat nahi khaenge.
can anyone tell me, Which data type should I take instead of Integer [ ] in C++?
take int but use memset or for loop and fill -1 instead
Int_max le
Sir your code is not working properly , I try to run same code on GFG and Leetcode compiler but it's return wrong ans ,Please rpl sir
Sir, I have one suggestion, after each videos if possible please confirm the time complexity.
Beta, TnS vala part level-1 main jaldi he cover krege.
@@Pepcoding Thank you Sir
In CPP,
How we can set value null in array?
Set it -1 and then check at last
what to return finally if we get -1 for Cpp
Sir your content and teaching way is best! But a small request to the editor is kindly don't insert meme content or any other distraction in between, it just breaks the flow and concentration. I hope it's understandable. Thanks
Please solve coin change problem also
Abhi abhi solve ki hai, aj raat ko dalegi.
I think the code fails for testcase 2,0,0
Sir climb with variable jump me humne destination index ko 1 dia tha par isme 0 dia aisa kyu yw problem hai minimum number of moves to reach destination
yar jab path pooche hain na to 1 lenge kyunki destination to destination 1 path hota hai (keep standing and don't move). Jab steps ya minimum moves poocha jae to 0 hota hai (kyunki destination to destination 0 move lagta hai)
Question hi nhi smjhe mtlb ap
n=10
arr = 2 ,3 ,1, 1, 2 ,4, 2, 0 ,1 ,1
Sir is test case ka ans 4 h lain code 5 bata raha h
There is logical mistake i guess , if you are at the top then you can have 0 move to reach the top. so correction you can make is dp[n-1] = 0 and start outer loop from n-2;
class Solution {
public int jump(int[] nums) {
int n = nums.length;
Integer[] dp = new Integer[n+1];
dp[n] = 0;
dp[n-1] = 0;
for(int i =n-2;i>= 0;i--)
{
if(nums[i] > 0)
{
int min = Integer.MAX_VALUE;
for(int j =1;j
Sir, CPP mein dp[] ko null kaise karein?? agar isko 0 lege toh dp[i] kabhi koi dusra value nahi ayega other thn 0 and also bool array liya toh sirf true or false lega...how to solve this problem?
jump array me jaha jaha 0 h, usko INT_MAX kardo.
Abe bhai vector use kr na 🙃🙃🙃
isma humna bada INTEGER WRAPPER CLASS ISLIYA LIYA NA TAAKI MINIMUM OF 0 SA BACHH SAKAA
i came from C++ and solved 1-2 question in java now get stuck in java and solve 15 questions using java
Python code for above problem
import math
def takeInput():
arr = []
for _ in range(int(input())):
arr.append(int(input()))
return arr
def compute(arr):
n = len(arr)
dp = [math.inf]*(n+1)
dp[n] = 0
for i in range(n - 1, -1, -1):
minVal = math.inf
for j in range(1, arr[i] + 1):
if i + j < len(dp):
minVal = min(minVal, dp[i + j])
if minVal!=math.inf:
dp[i] = minVal + 1
return dp[0]
print(compute(takeInput()))
Is not this problem kind of same like min. Jumps to reach end of array ?
Glad it was helpful, for better experience and well organised content sign up on nados.io and start learning.
Sir, is memorization technique is not easy as compared to tabulation ?
Yes it is, and that is why I think it is not advisable.
@@Pepcoding so should we use it or not
Sir please rectify cpp issue in editor. It is not executing the code in cpp
I will get it checked.
@@Pepcoding still problem persists ans is not coming
@@Code_Note Still the same problem right?
What is wrong here?
@@aryanadi8494 i have to check bro , I switched the platform for practicing problems.
Can we do this using recursion??
Hanji beta
sir agr code c++ me bhi mil jata or mza ajata.
vectordp(n+1,INT_MAX) use kr le bhai bas baaki sab same hai...
But sir this will have O(n^2) time complexity for worst case
O(n^2) bhai
Can we solve this by memoization ?
You can refer to nados.io for better experience and well curated content. You will get multiple of options too. Even you can post your queries on community section of NADOS.
Sir esme kitna hoga time complexity and space complexity
Beta n
@@Pepcodingbut if i have an array of size 3 , all the elements in array are 3 , then there will be n(n+1)/2 comparisons ?
@@Pepcoding sir n kaise , please reply asap
mai soch rha hu sir aap ye course nhi late to hamara kya hota...thank u sir..
lana he tha. Koi to lata he, humne la dia.
@@Pepcoding 😍🙏🙏
Sir thoda video uploading ki speed and frequency increase kar dijiye please
ji, poori koshish rahegi. mai bhi tabhi satisfy hounga jab roj 25 videos dalein.
@@Pepcoding much needed sir .
Bhaiya if I solves 1000+ problems on leetcode. Will that be enough?
yes
etne me to amazon nikal jaega
Dur se sb kuch acha lgta h
@@anjneykumarsingh4461 🤣🤣
I have a doubt that can this problem be solved using memoization?
For better insight, visit nados.io, post your doubts, community will help you out there.
@@Pepcoding okay thanks
Sir when I run the loop from ar[i] to 1:
for(int jumps = ar[i]; jumps >= 1 && i + jumps
In the first case u are terminating the loop as soon as the array has jump allowed less than 1 in this case like in 4 we aren't allowed to make any jump and in your code at position 4 the loop will break
The problem can be solved using the opposite direction, (traveling from 0 to n).
Thanks to Leetcode problems Min Cost Climbing Stairs and House Robber. Solving those problems few days ago, I got this idea.
My solution:
=======
n = int(input())
arr = []
for i in range(0, n):
c = int(input())
arr.append(c)
dp = [500]*(n+1)
dp[0] = 0
for i in range(0, n):
if arr[i]!=0:
j = 1
while j
Sir I think, It is not Optimised solution for this problem
Sir this program fails in this case: n=6, arr= 1 4 3 2 6 7. Actual o/p= 3, Expected= 2
There's one more case where it fails..
10
2 3 1 1 2 4 2 0 1 1
Actual Output = 5 Expected = 4
dry run theek se karo 3 is correct
@@RohitSingh-so5yf dry run theek se karo 5 is correcttttttt
make dp array of size n not n+1
7:19
The same code is failing at GFG
10
2 3 1 1 2 4 2 0 1 1
Its Correct output is:
4
And Your Code's output is:
5
problem link ?
Time complexity iski n square nahi hogi ? If I have an array of size 3 and each array has 3 in it
Yes
@@Pepcoding thank you sir
Sir why is int array of Dp not gonna work in this problem?
int array in by default initialised with 0 .
Integer array are initialized by null.
Since we need null ,thus we use integer array
sir please share notes
daal rhe hain ji
@@Pepcoding thankuu sir
They say DP is counter intuitive and tough. Me: Ha Ha. Just see Sumeet sir's video.
Haha..nice
If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
bhut confusion ho raha ab to
This fails for input {2,3,1,1,2,4,2,0,1,1}
Solution
static void minJumpsTab1(int[] arr) {
int[] dp = new int[arr.length + 1];
Arrays.fill(dp, 0);
for (int i = arr.length - 1; i >= 0; i--) {
int jump = arr[i];
int min = Integer.MAX_VALUE;
for (int j = 1; j
SUMEET SIR , saying humbly u G.O.A.T
but in this problem we should make dp[n] and intialize dp[n-1]=0 because this TEST CASE : N=7 VALUES : 1 2 0 3 0 0 0 ....will show incorrect output
c++ anyone solved it by initializeing to -1 ????????????????????????????????????????????????????
me
Samajh rahe ho 🤣 🤣 🤣 🤣 🤣 🤣 🤣 🤣 🤣 🤣 🤣
haha
Hello sir,
for this input
2 3 1 1 4
our DP solution is giving answer as 3
but actual answer is 2 . ( 2->3->4). 2 jumps
for doubt support, you can consume this same content on nados.pepcoding.com
Visit: nados.pepcoding.com/ where many coders like you, who can help you with your doubts, are active on a daily basis.
Also to be updated regarding any free opportunities we have follow us on insta as well:
instagram.com/pepcoding/
Bhai 4th position ke baad ek move aur aayega coz we have to reach 5th position starting from 0th
no correct output is 3 only.