3154. Find Number of Ways to Reach the K-th Stair | Weekly Leetcode 398

[@namamishanker7167]

Great explanation I watch your videos after every contest

[@AnandKumar-kz3ls]

thanks mohan learn lots of new thing in just 30 minutes now I got why my some of solution got tle when I tried to solve shortest path using dfs + dp instead of bfs because my recursion got stuck into cycle.

[@AkshatJain-to8fe]

Base case can be i >= k+2 and value be 0

[@dawodujohnson]

Outstanding as always

[@AnandKumar-kz3ls]

great explanation as always i didnt get how you get no of distinct values for i

[@iWontFakeIt]

Why the values of distinct values of "i" is of order log(k) ? Please explain.

[@mbm.editzz]

legendary

[@rengoku448]

Why is the limit 2*k not k+1 like if I reach k+1 it should be sufficient

[@codingmohan]

This is for smaller Ks - Honestly, I didn't put much thought on exact limit as it wouldn't affect the time complexity much.
But I think K+1 might work as well as for k=1, both K+1 and 2K are equal . Try once.

[@solosanskar490]

i did it like this post contest
class Solution {
public:
unordered_map dp;
int helper(long long stair,int jump,bool canDec,int &k){
if(dp[stair][jump].find(canDec)!=dp[stair][jump].end()){
return dp[stair][jump][canDec];
}
if(stair==k){
int ans = 1;
if(canDec==true && stair!=0){
ans += helper(stair-1,jump,false,k);
}
if(stair + (1LL