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.
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.
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
Great explanation I watch your videos after every contest
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.
Base case can be i >= k+2 and value be 0
Outstanding as always
great explanation as always i didnt get how you get no of distinct values for i
Why the values of distinct values of "i" is of order log(k) ? Please explain.
legendary
Why is the limit 2*k not k+1 like if I reach k+1 it should be sufficient
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.
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