The Recursive Staircase - Top Down & Bottom Up Dynamic Programming ("Climbing Stairs" on LeetCode)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
Question: You are climbing a staircase. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? (n is always a positive integer).
This is a classic problem. Let us tackle it thoroughly, there are many ways to do this that form the basis for how we do other problems bottom up with a DP table or top down with memoization.
The key with a problem like this is to instantly recognize that this turns into a series of subproblems, it is very similar to the Fibonacci sequence calculations.
Approach 1 (Top Down Recursion w/o Memoization)
Example:
n = 4
Let f(n) be the number of ways to climb n steps if we can take 1 or 2 steps.
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)
Base case: f(0) = 1 and f(any negative number) = 0
Notice that we are resolving subproblems that we already have an answer to and hence we are wasting time.
Complexities
Time: O( 2 ^ n )
Each recursive call can spawn 2 more calls, depth of the recursion tree is n. This is a loose bound, a tighter one is around O( 1.62 ^ n )
Space: O( n )
Call stack max depth. Max depth of the recursion tree goes n calls deep.
Approach 2 (Use Memoization On Top Down)
Memoization: An optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Dynamic programming is all about storing the answers to previous sub-problems to speed up our runtimes by avoiding repeating work that has already been done.
Complexities
Time: O( n )
We cancel out many of the repeated calls that we might have made leading to us to have a linear time complexity.
Space: O( n )
Call stack max depth. And we will still have the dp table.
Approach 3 (Dynamic Programming Array)
DP is all about caching the answers to previous work and using it in current work.
dp[n] denotes the number of ways to climb n steps if we can take 1 or 2 steps.
dp[n] = dp[n - 2] + dp[n - 1]
The answer to n is the sum of the answer between two things:
our last step to n is 2 long
our last step to n is 1 long
Base Cases: dp[1] = 1 and dp[2] = 2
Complexities
Time: O( n )
A for loop making n - 2 iterations
Space: O( n )
We will be holding n + 1 entries in a dp array
Approach 4 (Fibonacci Number)
We notice that this is just the Fibonacci series. We can just use local variables to keep track of the items 1 and 2 behind where we stand.
Complexities
Time: O( n )
Still solve up to n subproblems.
Space: O( 1 )
No more dp array, we just use constant local variables
All other approaches are esoteric and are not practical in an interview, these include:
- Using Binets Method & matrix multiplication
- Using the mathematical, non-recursive, version of the Fibonacci Formula
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Видео The Recursive Staircase - Top Down & Bottom Up Dynamic Programming ("Climbing Stairs" on LeetCode) канала Back To Back SWE
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
Question: You are climbing a staircase. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? (n is always a positive integer).
This is a classic problem. Let us tackle it thoroughly, there are many ways to do this that form the basis for how we do other problems bottom up with a DP table or top down with memoization.
The key with a problem like this is to instantly recognize that this turns into a series of subproblems, it is very similar to the Fibonacci sequence calculations.
Approach 1 (Top Down Recursion w/o Memoization)
Example:
n = 4
Let f(n) be the number of ways to climb n steps if we can take 1 or 2 steps.
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)
Base case: f(0) = 1 and f(any negative number) = 0
Notice that we are resolving subproblems that we already have an answer to and hence we are wasting time.
Complexities
Time: O( 2 ^ n )
Each recursive call can spawn 2 more calls, depth of the recursion tree is n. This is a loose bound, a tighter one is around O( 1.62 ^ n )
Space: O( n )
Call stack max depth. Max depth of the recursion tree goes n calls deep.
Approach 2 (Use Memoization On Top Down)
Memoization: An optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Dynamic programming is all about storing the answers to previous sub-problems to speed up our runtimes by avoiding repeating work that has already been done.
Complexities
Time: O( n )
We cancel out many of the repeated calls that we might have made leading to us to have a linear time complexity.
Space: O( n )
Call stack max depth. And we will still have the dp table.
Approach 3 (Dynamic Programming Array)
DP is all about caching the answers to previous work and using it in current work.
dp[n] denotes the number of ways to climb n steps if we can take 1 or 2 steps.
dp[n] = dp[n - 2] + dp[n - 1]
The answer to n is the sum of the answer between two things:
our last step to n is 2 long
our last step to n is 1 long
Base Cases: dp[1] = 1 and dp[2] = 2
Complexities
Time: O( n )
A for loop making n - 2 iterations
Space: O( n )
We will be holding n + 1 entries in a dp array
Approach 4 (Fibonacci Number)
We notice that this is just the Fibonacci series. We can just use local variables to keep track of the items 1 and 2 behind where we stand.
Complexities
Time: O( n )
Still solve up to n subproblems.
Space: O( 1 )
No more dp array, we just use constant local variables
All other approaches are esoteric and are not practical in an interview, these include:
- Using Binets Method & matrix multiplication
- Using the mathematical, non-recursive, version of the Fibonacci Formula
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Видео The Recursive Staircase - Top Down & Bottom Up Dynamic Programming ("Climbing Stairs" on LeetCode) канала Back To Back SWE
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
![Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition](https://i.ytimg.com/vi/iOaRjDT0vjc/default.jpg)
![The Change Making Problem - Fewest Coins To Make Change Dynamic Programming](https://i.ytimg.com/vi/jgiZlGzXMBw/default.jpg)
![11. Top-Down vs. Bottom-Up (Dynamic Programming for Beginners)](https://i.ytimg.com/vi/_i_nTcwyh-E/default.jpg)
![Climbing Stairs | LeetCode 70 | Google Coding Interview Tutorial](https://i.ytimg.com/vi/UyDyc6yV1iQ/default.jpg)
![Compute The Next Permutation of A Numeric Sequence - Case Analysis ("Next Permutation" on Leetcode)](https://i.ytimg.com/vi/quAS1iydq7U/default.jpg)
![](https://i.ytimg.com/vi/7yC1aN87Ydo/default.jpg)
![GOOGLE CODING INTERVIEW QUESTION - CLIMBING STAIRS (LeetCode)](https://i.ytimg.com/vi/uHAToNgAPaM/default.jpg)
![What Is Dynamic Programming and How To Use It](https://i.ytimg.com/vi/vYquumk4nWw/default.jpg)
![The Quicksort Sorting Algorithm: Pick A Pivot, Partition, & Recurse](https://i.ytimg.com/vi/uXBnyYuwPe8/default.jpg)
![5 Simple Steps for Solving Any Recursive Problem](https://i.ytimg.com/vi/ngCos392W4w/default.jpg)
![Find The Second Largest Item - Heap & Tracking Approach (Beginner Big N Interview Question)](https://i.ytimg.com/vi/NheWPxGpoxQ/default.jpg)
![A slacker was 20 minutes late and received two math problems… His solutions shocked his professor.](https://i.ytimg.com/vi/O_bVUeQw38c/default.jpg)
![19. Dynamic Programming I: Fibonacci, Shortest Paths](https://i.ytimg.com/vi/OQ5jsbhAv_M/default.jpg)
![Amazon Coding Interview Question - Recursive Staircase Problem](https://i.ytimg.com/vi/5o-kdjv7FD0/default.jpg)
![Math Has a Fatal Flaw](https://i.ytimg.com/vi/HeQX2HjkcNo/default.jpg)
![Total Ways To Decode A String - Recursive Dynamic Programming Approach ("Decode Ways" on LeetCode)](https://i.ytimg.com/vi/YcJTyrG3bZs/default.jpg)
![Depth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms](https://i.ytimg.com/vi/TIbUeeksXcI/default.jpg)
![Total Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)](https://i.ytimg.com/vi/RlXtTF34nnE/default.jpg)
![LeetCode 70. Climbing Stairs - Interview Prep Ep 72](https://i.ytimg.com/vi/ZMNRb9TYiQM/default.jpg)
![Serialize & Deserialize A Binary Tree - Crafting Recursive Solutions To Interview Problems](https://i.ytimg.com/vi/suj1ro8TIVY/default.jpg)