algorithmrecursionfibonacci# Staircase problem - Varying base cases in different coditions

This questiion is related to Staircase problem - explanation of recursive approach

But about the base cases.

One variation of the problem is as follows:

There are n stairs, a person standing at the bottom wants to climb stairs to reach the nth stair. The person can climb either 1 stair or 2 stairs at a time, the task is to count the number of ways that a person can reach at the top.

the base condition goes like this:

```
if( n <= 1) return n
```

Makes sense as when there's 1 step, there's only one way to climb. So is the case in which there's 0 steps to climb.

But in the variation of the same problem, where the person can take 1, 2 or 3 steps, the base becomes like this:

```
if(n<0)
return 0;
if(n == 0)
return 1;
```

So if there are 0 steps to climb there's one way here. Why?

Another thing I notice, there's emphasis on negative n in the latter case, i.e it has to return 0 in that case while in former it's not explicitly handled. Does it not occur in former?

Solution

It's like Fibonacci. If f(n) is the number of ways of climbing up n steps, and we can take up to k at a time, then f(n) = f(n-1) + f(n-2) + ....+ f(n-k), where f(0) = f(1) = 1, and f(anything negative) is 0.

The reason is, every combination of steps which leaves us at n has a last step of size 1 or 2 or 3 or ... or k, except if n is less than k then we ignore or treat as 0 anything from n+1 up to k.

e.g., if k=3 and f(n) is the number of ways of reaching the n'th step, then f(7) either ends with a size 1 step in f(6) ways, a size 2 step in f(5) ways, or a size 3 step in f(4) ways.

But, f(2) can't end with a step of size 3, so we can either only calculate f(0) + f(1), or treat f(anything negative) as being 0. The former is slightly more efficient, the latter is simpler.

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array