Climbing stairs

• Striver series, https://www.youtube.com/watch?v=mLfjzJsN8us
• Tabulation →
• Log n approach →
• Try all possible ways OR Best way → Try Recursion
• Striver Recursion 7 mentions the same.
• Shortcut:
  1. Try to represent problem as index. (For both Arrays and non Array problem)
  2. Do all possible stuff on that index according to the problem statement.
  3. Sum of all stuffs → count all ways min (of all stuff) → Find min

Connect code with intuition

• If standing at 0th stair you can go to only to 1, so return 1.
• There are two options you can just one or jump two so call recursion by subtracting 1 or 2 from the index. Name them left and right recursion, left = f (index - 1), right = f(index - 2)
• Answer here:
• This is similar to Fibonacci Numbers Algorithm
• DSA_trick If the input size is 10^18 you can’t do it in n. so need to you do Matrix Exponentiation

With Memoization

// A simple recursive function to find number of ways to reach the nth stair
 
function countWays(n, dp)
{
	if (n <= 1)
		return dp[n] = 1;
 
	if(dp[n] != -1 ){
		return dp[n] ;
	}
	dp[n] = countWays(n - 1, dp) + countWays(n - 2, dp);
	return dp[n] ;
}
 
 
// Driver Code
 
let n = 4;
let dp = new Array(n+1).fill(-1) ;
console.log("Number of ways = " + countWays(n,dp));
 

Withtabulation

function countWays(n)
{
	let dp = [];
	dp[0] = 1; 
	dp[1] = 1;
	for (let i = 2; i <=n; i++)
	{
		dp[i]=dp[i-1]+dp[i-2];
	}
	return dp[n];
}
 
 
	// Driver Code
	let n=4;
	console.log("Number of ways = " + countWays(n));
 

log n with Matrix Exponentiation

• Can skip this, not to get into to much advanced stuff. There are lot more concept that as more important as per interview perspective.