Блог пользователя samsidx

How to solve this please help...
Автор samsidx, 10 лет назад, По-английски

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
  • Проголосовать: не нравится

»
10 лет назад, # |
← 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)

→ Ответить