Untitled
unknown
plain_text
a year ago
622 B
4
Indexable
class Solution { public: int waysToReachStair(int k) { map<array<long long,3>,int> dp; const long long bound=1000000000; function<int(long long,int,int)> rec=[&](long long curr,int jump,int flag){ if(curr>bound) return 0; if(dp.find({curr,jump,flag})!=dp.end()) return dp[{curr,jump,flag}]; int ans=0; if(!flag and curr>0){ ans+=rec(curr-1,jump,1); } ans+=rec(curr+(1LL<<jump),jump+1,0); return dp[{curr,jump,flag}]=ans+(curr==k); }; return rec(1,0,0); } };
Editor is loading...
Leave a Comment