Output for A = 0 is wrong


For A=0, ans should be 0 not 1. So the dp solution is wrong as for the formula used to calculate only works if it is 1 for A=0. Think for A=2, it wont be ans = func(A-1) + func(A-2) i.e. func(2) = func(1) + func(0) = 1 + 0 = 1 which is wrong.


Look what constraint is given:

1 <= A <= 36


for A=0 , ans 1 is correct because for reaching at 0th stair you don’t have to make any move, which is considered as 1 way


using that logic, for A=1 answer should have been 2. As, one step for reaching stair 1 from start and then 1 step for reaching stair 1 from stair 1(which is considered as one step from your argument)

Note: for A = 1 ans = 1 (This is correct) please follow the constraints.


For A=0, not making any move is one way and it is not that we are moving from 0th step to 0th step.
And by the way, u can see given A>=1


Since the constraint is 1 <= A <= 36, the output for A=0 is undefined. I think you can just ignore A=0, and start the for-loop with i = 3.