We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Same solution in PyPy3! Speed up was enough to pass all cases but python3 is still too slow.
Idea is to check if you have already calculated value for n, and if not then to add it to the dictionary.
My solution uses recursion and memoization (Dynamic Programming). It's more readable if you see it this way:
#include<vector>#include<iostream>usingnamespacestd;vector<int>W(37,0);intf(intn){if(W[n]!=0)//It had already been calculatedreturnW[n];else{if(n>=3)W[n]=f(n-3)+f(n-2)+f(n-1);elseif(n==1orn==2)W[n]=n;else//n == 0W[n]=1;//these last two are this: (n>>1)+1}returnW[n];}intmain(){intn;cin>>n;//ignoring swhile(cin>>nandcout<<f(n)<<endl);//Here I read and write until the whole input stream has been readreturn0;}
I got your entire DP code. Only one doubt I have and it is related to ways to calculate 3 steped staircase.
Code says it is w[3] = w[0]+w[1]+2[2]=0+1+2=3 where as one can climb it with four different combinations.. Here it is 1 (1+1+1), 2 as (1+2), 3 as (2+1) and fourth as (3) all 3 steps in a go.
Recursion: Davis' Staircase
You are viewing a single comment's thread. Return to all comments →
You can use recursion to solve this problem with a cache.
I did the same but I cached the 3 recursions everytime... sigh
give input 1 30 your code will crash!
Same solution in PyPy3! Speed up was enough to pass all cases but python3 is still too slow. Idea is to check if you have already calculated value for n, and if not then to add it to the dictionary.
That was useful @adding stuff to dictionary.
I totally did the same thing.
Did a similar python approach
and climb(240) returns 2028382748046767387253483395022331055100978649577557465746184401
with no pain at all ;)
You can also use the @functools.lru_cache() decorator.
Worked like a charm in Python3! No problem with big numbers too.
I also did it like yours
could you please explain you code??
My solution uses recursion and memoization (Dynamic Programming). It's more readable if you see it this way:
Sorry my english
Thank you for your detailed explanation.
I got your entire DP code. Only one doubt I have and it is related to ways to calculate 3 steped staircase.
Code says it is w[3] = w[0]+w[1]+2[2]=0+1+2=3 where as one can climb it with four different combinations.. Here it is 1 (1+1+1), 2 as (1+2), 3 as (2+1) and fourth as (3) all 3 steps in a go.
Am i missing something?
A simple version to your code:
Niiiiiice! The map fixed my termination due to timeout!
I am not able to understand this solution. Can you please explain?
Check out memoization and dynamic programming: https://www.youtube.com/watch?v=P8Xa2BitN3I