Untitled

/*
this is classic recursion problem but not able to find the dp states can't come up with dp solution 
just doing what they asks
so, hence ends up with tle.
*/
class Solution {
    public int waysToReachStair(int k) {
        return Answer(k,false,0,1);
    }
    public int Answer(int k,boolean down,int jump,int step)
    {
        int answer=0;
        answer=step==k?1:0;
        if(step-1>k)return 0;
        int first=0;
        if(!down&&step!=0)
         first=Answer(k,true,jump,step-1);
        int second=Answer(k,false,jump+1,step+(int)Math.pow(2,jump));
        return answer+first+second;
    }
}