A staircase has n steps. You can scale the stairs by taking steps one or two at a time. How many ways are there to scale the steps?

If there are 0 steps, there is 1 possibility (you are already done).If there is 1 step, there is 1 possibility (you take one step).
If there are n steps, your first choice is either 1 step or 2 steps:Choice 1: the problem now exists for n-1 stepsChoice 2: the problem now exists for n-2 steps
Let f(x) be the number of ways of scaling x steps. You can now say that f(x) = f(x-1) + f(x-2) - the Fibonacci sequence.
This is an example of a dynamic programming question - a computer science topic for first-year Cambridge computer scientists, and my first interview question.

Answered by Oxbridge Preparation tutor

2024 Views

See similar Oxbridge Preparation Mentoring tutors

Related Oxbridge Preparation Mentoring answers

All answers ▸

For a murder conviction, it must be proved that the defendant intended to cause serious injury or death. The jury is directed to consider the 'normal meaning' of intent. What do you think that means and do you think it is a suitable direction for a jury?


What should I expect from an Oxbridge interview?


What is faith?


I know I am good at maths, but is there anything more I need to do in my interview to secure a place to study it?


We're here to help

contact us iconContact usWhatsapp logoMessage us on Whatsapptelephone icon+44 (0) 203 773 6020
Facebook logoInstagram logoLinkedIn logo

© MyTutorWeb Ltd 2013–2025

Terms & Conditions|Privacy Policy
Cookie Preferences