Climbing Stairs with Jumps using Dynamic Programming | Recursive Staircase Problem

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 Climbing Stairs problem with variable jumps using dynamic programming and tabulation method. This problem is also referred to as Recursive Staircase Problem and an asked problem in Amazon. 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.
4. You are required to print the number of different paths via which you can climb to the top.
For a better experience and more exercises, VISIT: www.pepcoding....
#dp #dynamicprogramming #climbstairs
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education

[@manishkumarsharma6507]

I regret why i knew this channel now.... I should have aware of this channel 1 year back..... Best coding channel on youtube ..... With free content

[@karmakaraayon4238]

same yar 🥹

[@faizanhaider3953]

Same yr

[@mdarman0063]

Same case with me😢

[@arfataara4329]

Highly under appreciated channel. Learning a lot.

[@Pepcoding]

thank you beta. agar content acha lag rha ho to review daal do g.page/Pepcoding/review?rc

[@adityadev2825]

Marvelous playlist 🔥 For those who are confused on how to travel in reverse direction i.e, from 0 -> 6. Problems can be solved in any direction based on the meaning you assign to each cell. Code for reverse order: int[] dp = new int[n+1]; dp[0] = 1; for(int i=0; i

[@tanishqyadav6053]

The Memoized as well as Tabulated code in CPP for this question : #include using namespace std; long long int Sol_Memo_Util( long long int k, long long int n , vector &arr,vector &memo) { if(k>n) return 0; if(k==n) return 1; if(memo[k]!=0) return memo[k]; long long int res = 0; for(long long int i=1;i=0;i--) { for(long long int j=1;j

[@PiyushKumar-po8bj]

can this be done using recusion ?

[@trainwithguneet]

You are super underrated. I did a variation of this question earlier on GFG (min jumps to reach end of array).

[@sairagavender]

i am just watching this cause i am bored at this point even though i am not a cs student

[@seemaalam3127]

First dialogue...lol...😂😂 Lots of love for the way u teach...😍

[@Pepcoding]

Thank you so much 😀Please visit nados.pepcoding.com for more such amazing content :)

[@YashGupta-zh8fz]

Wow sir Glad to finally find this channel and your videos Your teaching is excellent

[@Pepcoding]

Padhte rahie. Learn well.

[@sachinvishwakarma6607]

Please put this intro in every explanation 😭😂😂😂

[@nightingale180]

Hey, the content is good but the memes in b/w become too loud as compared to your voice so have to adjust the sound for that..just afeedback. Else thank you so much for your effort, really appreciate that..

[@mayankverma3690]

Sir in this question the direction is from right to left in tabulation , can we solve it using tabulation using the left to right direction??

[@Pepcoding]

Hanji beta, dono tarf se kr skte h. Dp sochne ka tarika alg h aur dp ka meaning change ho jayega bus.

[@tejaswinisingh6263]

Sir , which method is better tabulation or memoization, if I want to do in one way only:)

[@amantiwari1481]

Memoization because it is difficult and sometime illogical to solve in tabulation method. But if you are good with recursion then you can solve dp easily with proper logic.

[@prateekchaurasiya3877]

Sir really wow.... and memes in between are lit

[@Pepcoding]

Ji. Keep giving us a feedback. Usi tarah ka content bnaenge jo aapko jyada pasand aaega.

[@tushar_kushwaha]

sir app apni marketing pe bhi dhyaan dijiye...aur aap bhi jyda se jyda apne channel pe aaya kare aur bhi short videos banaye. See coding ninjas channel for reference. Baaki aap jo kr rhe hai bdiya hai. Thank you.

[@dark_techyy]

Sir mai apka regular student hu...🙏..pr aapne kaha tha agr recursion use ni kiya to dp nhi h vo...or ye tabulation wale method me jb loop use kr rhe h to vo dp hai k ni?🤔

[@pravinmudaliyar3421]

Memoized as well as tabulated 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){ return 0; } if(dp[curr] != 0){ return dp[curr]; } int ways = 0; for(int i=1; i=0; i--){ int jumps = arr[i]; for(int j=1; j

[@pragatirawat1103]

Some of you are asking for memoization code for the same problem. Commenting below the memoized code. Please have a look :- import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner scn = new Scanner(System.in) ; int num = scn.nextInt() ; int[] qb = new int[num+1]; int n = 0; int[] arr = new int[num] ; for(int i = 0; i < arr.length; i++){ arr[i] = scn.nextInt() ; } int cp = countPaths( num,n,qb,arr ); System.out.println(cp); } public static int countPaths( int num,int n,int[] qb,int[] arr ){ if(n == num) { return 1; } else if(n > num) { return 0; } if(qb[n] > 0) { return qb[n]; } int cp = 0; for(int i = 1; i

[@satisfyingwalks4010]

thank you for this!

[@curiosity9861]

I have checked it multiple times but I am getting 15 as an output for the test case provided in the Pepcoding website where the output for that test case is 5 .Can you please explain that. testcase

[@sadmansakib007]

you need to step on "just outside" the array. hope that helps

[@aaswinsinha3698]

Sir please ek video banao ki how to identify a problem can be solved with dp or not?

[@AnkitSharma-wj2tb]

Superb sir. Nice way of teaching 😂😂😂🔥🔥❤️❤️❤️

[@Pepcoding]

Thanks a lot 😊

[@vaibhavaggarwal5710]

It canbe done as bottoms up as well

[@Hephaestus-q9h]

the compiler on site does not work?

[@swapnilpadaya163]

sir iska recursive solution ka video banna do na please.

[@ztrixx3280]

I tried a lot, but couldn't do it using recursion. Need help!!

[@maxbrooke9411]

same

[@utkarsh_108]

@@maxbrooke9411 koini mai karke bhejta hu

[@utkarsh_108]

int climbStairsWithVariableJumps(vector arr, int i, vectorqb){ // write your code here if(i==arr.size()){ qb[i]=1; return qb[i]; } if(qb[i]!=-1){ return qb[i]; } int count=0; for(int step=1; stepn; vector arr(n); vector qb(n+1,-1); for(int i = 0 ; i < n ;i++){ cin>>arr[i]; } cout

[@nivealokhande2153]

@@utkarsh_108 bhej jldi saal hogyaa

[@himanshuchhikara4918]

Hahaha 😂😂 mst editing hai sir mzza aagya

[@Pepcoding]

Hahaha 😂😂

[@TheShantanu1395]

Python solution for above problem def takeInput(): arr = [] for _ in range(int(input())): arr.append(int(input())) return arr def compute(arr): n = len(arr) dp = [0]*(n+1) dp[n] = 1 for i in range(n - 1, -1, -1): for j in range(1, arr[i] + 1): if i + j < len(dp): dp[i] += dp[i + j] return dp[0] print(compute(takeInput()))

[@CD-xd6fm]

what will happen in j loop if arr[i] =0 won't it give error ? (i am saying about when we can go 0 steps ahead)

[@harshitgupta8844]

how to write recursive code of this code. or how to solve this question via recursion please explain

[@lifeskills5913]

Is there any difference between this question and question of climbing stairs with 1 or 2 jumps only?

[@kartikpapney9250]

Placement k baad aapse milne aaunga... Aapke charan sparsh krne hai 😍

[@Pepcoding]

jarur milne aao... placement k baad toh mithaai bhi leke aana! :)

[@mkshubham1386]

Placement hui kya bhai?

[@saichaithrik7134]

respected sir i have seen so many teachers during my learning process but u sir are the best of the bunch sir thanks for all the help.

[@anuragnegi6423]

ye question recursively kardiya 1st ques ki tarah, ye bhi dp mein included h??

[@Pepcoding]

hanji DP mei bhi hai

[@horridhenry6789]

kaise bhai??

[@NiteshKumar-nx2fu]

bhai recursion ka code comment krdo please...

[@RAHUL-gf3ft]

bro pls send ur recursion code

[@geetanegi2736]

Sir time complexity kab sikhayenga sir. Nice content sir .god bless u sir.

[@Pepcoding]

Beta, jaldi he daalege and thankyou! I am glad you liked it. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@mahavirsingh5790]

Iterator I = "Meri shaktiyo ka galat istemal hua hai maa" 😀😀

[@Pepcoding]

Haha..😋

[@sahilgupta9378]

swaad aagya sir aapke tabularization se

[@Pepcoding]

Keep learning and keep loving Pepcoding😊 If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@programmingexam9178]

Why not in english?

[@satyamgupta1416]

sir is question mah direction q right to left li h jabki phle vale mah left to right li thi

[@AbhishekSingh-qx1km]

What if arr[0]=0??

[@yashparmar5722]

Great❤

[@omeshpal4249]

you are making a complex problem very easy and simple.. the way you are explaining is phenomenal.

[@sakshamsrivastava6280]

IF YOU THINK IT THROUGH, IT MAKES QUITE A LOT OF SENSE. tHANKYOU sUMIT SIR

[@gauravrewaliya3269]

when to use tabulation and when memorization??

[@dayamalik6025]

Super super super super teacher

[@dayamalik6025]

Hello chachu your Aryan

[@Pepcoding]

Hello betu, Thank you. Yours, Chachu

[@nivealokhande2153]

@@dayamalik6025 abee har video mai kyaa lga rkha hai hello

[@anjneykumarsingh4461]

Sir,can every problem be solved by both tabulation and memoization

[@Pepcoding]

yes

[@samiulkhan3744]

no, to understand why it is not possible ,you can refer cheery pickup problem in the pepcoding level 2 dp series

[@PiyushKumar-po8bj]

can this be done using recusion ?

[@NiteshKumar-nx2fu]

sir how can we do this using recursion??

[@tusharmonga3253]

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine()); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.parseInt(br.readLine()); } int[] dp = new int[n + 1]; Arrays.fill(dp,-1); System.out.println(climbStairsVarJumpDP(arr,0,dp)); } public static int climbStairsVarJumpDP(int[] arr, int i, int[] dp) { if (i == arr.length) { return dp[i] = 1; } if (dp[i] != -1) return dp[i]; int count = 0; for (int step = 1; step

[@loserfruit9663]

@@tusharmonga3253 bro comment it in open section where everybody can see it,lots of student are facing problem in it using recursion

[@tusharmonga3253]

@@loserfruit9663 done

[@loserfruit9663]

@@tusharmonga3253 great work

[@zaid4you256]

@@tusharmonga3253 bro thanks for this present

[@tusharmonga3253]

Recursion code : import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine()); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.parseInt(br.readLine()); } int[] dp = new int[n + 1]; Arrays.fill(dp,-1); System.out.println(climbStairsVarJumpDP(arr,0,dp)); } public static int climbStairsVarJumpDP(int[] arr, int i, int[] dp) { if (i == arr.length) { return dp[i] = 1; } if (dp[i] != -1) return dp[i]; int count = 0; for (int step = 1; step

[@lakshmishree1281]

thanks a lot sir

[@manishkumarsah6898]

tusi great ho sir🙌

[@tamannamirza2133]

Sir, yahan ham 0 to 6 jaa rahein hain matlab shorter problem hua 6 to 6 and so on. Whereas last problem mein ham 0 to 0 short problem maan rahe the ye thoda confusion hai sir please clear kardijiye :( Dono problems mein ham stairs climb hi kar rahe hai lekin phir directions alag kyun

[@Pepcoding]

beta sikhane ke liye kia hai, ki dono tareeke se kar sakte hain. agar meaning alag dia to smaller problem doosri taraf banne lagegi aur travel ki driection badal jaegi. Sare questions dono tareeke se kie ja sakte hain. It all depends on meaning of cell

[@tamannamirza2133]

@@Pepcoding Okay sir thank you sooo much for taking time to solve my doubt. Abhi sab clear hogaya :) Feel really blessed to have found your channel

[@aahanaganjewar9951]

Recursive Solution class Solution { public boolean canJump(int[] nums) { return jump(nums, 0); } public boolean jump(int[] nums, int idx) { if (idx == nums.length - 1) { return true; } boolean ans = false; for (int i = 1; i

[@priyankajain4223]

here we need to return count, not true and false, so how will it work

[@aahanaganjewar9951]

@@priyankajain4223 oh really sorry!

[@priyankajain4223]

@@aahanaganjewar9951 Are you following this playlist?

[@aahanaganjewar9951]

@@priyankajain4223 yes!

[@rohitnehra9519]

Big fan maam

[@pankajkaushik7912]

Sir dp(i)+=dp(i+j);.....Sir isme + symbol use kyun Kiya.....kyunki if we want to find dp(6),then dp(6)=dp(6)+dp(7)....Please help me sir

[@Pepcoding]

Hanji, sahe smjhe aap.

[@pankajkaushik7912]

@@Pepcoding but sir dp(6) pehle hai hi nhi hmare pass

[@KeshavKumar-zk3uh]

@@pankajkaushik7912 bhai dp(6) last element tha array ka, to wha jane ka ek rasta hamesha hota hai.

[@pankajkaushik7912]

@@KeshavKumar-zk3uh Bhai kaise hota hai raasta elaborate?

[@KeshavKumar-zk3uh]

@@pankajkaushik7912 generally ese me base cases me one leke chalte h ki 6 se 6 jane ka rasta ek hi taki uske realtive me ham soch paye fir 5 se 6 jane k kitne tarike honge,,,,confirm nhi h mujhe bhi itna hi samjh aaya

[@divyanshsingh6163]

sir can you plz write dp[ i ] += dp[ i + j ] ; in some other way??

[@Pepcoding]

Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.

[@crackthecode1372]

Awesome Video sir , Thanks a lot for uploading, sir just one suggestion: starting mein input output mention krdiya kijiye taaki pehle hum khud bji try krlein

[@Pepcoding]

ok ji

[@karmakaraayon4238]

🔥

[@Pepcoding]

Hope you love the explanation, for better experience and well organised content visit - nados.io

[@apoorvdixit2856]

sir content to bhot badhiya hai par , edting thodi zyada hogayi hai vedio mei. sorry sir but being one of your well wishers , isse brand value par thoda asar padhta hai, though content is best in the industry

[@Pepcoding]

Feedback is completely appreciated. Hanji, baad mei kar dia next videos mei.

[@darkdemise8273]

Mujhe to maza aaya beech beech mei pata chalta rehta hai computer ke dusri side bhi insaan hai.

[@shubhansusinghbhadoria8522]

i loved it ,i think it gives the real time experience of attending your class.

[@rishikeshrai6686]

Excellent sir

[@Pepcoding]

Keep watching

[@oqant0424]

excellent explanation

[@hemantsingh-zo3iw]

Excellent Sir

[@Pepcoding]

Keep watching

[@LegitGamer2345]

is the time complexiy order of n?

[@LegitGamer2345]

is it order of n square ? for example steps are 3 and we can jump 3 steps at each level starting from ground

[@anuragyadav1813]

❤️❤️❤️

[@darkdemise8273]

Sir aapke code se index out of bounds dikha raha thaa but pepcoding mei solutions mei 2 loop if(arr[i]>0)ki condition mei tha us se chal gayaa

[@SCRIPTSAG]

Recursive solution kya hoga sir eska

[@Pepcoding]

Beta formula recursion ka same rahega. Bnane ki koshish karo

[@SCRIPTSAG]

@@Pepcoding sir try ker rha hu mai soch pa rha hu recursion me kya kerunga but code me nhi ker pa rha hu subeh 4 bje se presan hu sir ab sirf tabultaion kerunga

[@ajay8315]

@@Pepcoding Hello sir i do every problem with memoisation(recursion) but don't get an idea about how to solve print path type problem recusively. Like print lcs

[@utkarsh_108]

@@SCRIPTSAG int climbStairsWithVariableJumps(vector arr, int i, vectorqb){ // write your code here if(i==arr.size()){ qb[i]=1; return qb[i]; } if(qb[i]!=-1){ return qb[i]; } int count=0; for(int step=1; stepn; vector arr(n); vector qb(n+1,-1); for(int i = 0 ; i < n ;i++){ cin>>arr[i]; } cout