CareerCup

Hi this is one of this problems that looks extremaly intimidating but somehow ends up being easy. If you check the number of ways for first few stairs length you can see that ways one can climb a staircase in respect to staircase length grows exacly like fibonacci number sequence. Lets say one step move = 1, and two steps move = 2. Possible ways for:
1 step staircase => 1 = {1} -> 1 way
2 step => 2 = {1+1}, {2} -> 2 ways
3 step => 3 = {1+1+1}, {1+2}, {2+1} -> 3 ways
4 step => 4 = {1+1+1+1}, {1+1+2}, {2+1+1}, {1+2+1}, {2+2} -> 5 ways
5 step => 5 = {1+1+1+1+1}, {2+1+1+1}, {1+2+1+1}, {1+1+2+1}, {1+1+1+2}, {2+2+1},
{1+2+2}, {2+1+2} = 8 ways.
ways(5) = ways(4) + ways(3) = 5 + 3 = 8.
I use sequencial code for optimal space complexity and additional array to store partial results to reduce time complexity to linear.

public static int countWays(int n)
	{
		if(n < 1)return -1;
		if(n == 1)return 1;
		int res[] = new int[n+1];
		res[1] = 1;
		res[2] = 2;
		
		for(int i = 3; i < n+1; i++)
		{
			res[i] = res[i-1] + res[i-2];
		}
		
		return res[n];
	}
	
	public static void main(String args[])
	{
		for(int i = 1; i < 10; i++)
		System.out.println(countWays(i));
	}

bogdan.zima is of course correct. A better way to prove is this identity.
suppose the no of ways you can take step n is defined by a function step(n).
Now, clearly, as only 1 or 2 step at a time are allowed, you could have reached step(n)
by :

one step + take rest of (n-1) OR two steps + take rest of (n-2) steps.
Tow independent count of choices, and thus must get added up.

Hence:
step(n) = step(n-1) + step(n-2) // this gives Fibonacci sequence.

You can generalize it.

// ZoomBA
$count = 0 
def count_stais( cur,path, max ){
   if ( cur > max ) return 
   if ( cur == max ){
     println( path ) ; $count += 1  
     return 
   }
   count_stais( cur + 1 , path + '->1' , max )
   count_stais( cur + 2 , path + '->2' , max )
} 
count_stais( 0 , '' , 4 )
println ( $count )

You can look at the recursive code, and decide the same!