samsidx's blog

By samsidx, 6 years ago, In English

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

 
 
 
 
  • Vote: I like it
  • -7
  • Vote: I do not like it

»
6 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it also can be solved by an n^2 dynamic programming which is kinda bad

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks.