### samsidx's blog

By samsidx, 6 years ago,

Now that he has grown up,Bit boy can climb atmost N steps at a time. Given the number of steps find the number of ways that he can climb the steps.

Input Format

First line of test case contains T , number of testcases. next T lines contains N , Number of steps.

Output Format

Print Answer for each test case in a newline

Constraints

1<=T<=100 1<=N<=500

Sample Input

2

1

2 Sample Output

1

2

• -7

 » 6 years ago, # | ← Rev. 2 →   +1 2^(n-1) is the answer because simply either you come from the back ones or climb directly to the n steps which is f(n) = f(n-1) + f(n-2) + f(n-3) ... + f(1) + 1 which we can simply deduce that it is 2 ^ (n-1) f(n) = f(n-1) + f(n-2) + ... + f(1) + 1 f(n-1) = f(n-2) + f(n-3) +... + f(1) + 1 f(n) -f(n-1) = f(n-1) f(n) = 2f(n-1) and since f(1) = 1 then f(n) = 2^(n-1)*f(1) = 2^(n-1)
•  » » 6 years ago, # ^ |   0 it also can be solved by an n^2 dynamic programming which is kinda bad
•  » » 6 years ago, # ^ |   0 Thanks.