# Recursion: Davis' Staircase

# Recursion: Davis' Staircase

goodengineer + 24 comments My first solution was a simple recursion with DP. Then I gave it more thought and came up with the following result:

Solving this problem is like solving the following recursion:

`A(n) = A(n - 1) + A(n - 2) + A(n - 3) A(1)=1; A(2)=2; A(3)=4.`

A(n) represents the number of ways he can climb a staircaise of height n.

This recursion is extremely similar to fibonacci so I thought a trick like matrix exponentiation should be possible, and apparently it is. The following equivalence is true:

`|A(n+2) A(n+1) A(n) | |1 1 0| |A(n+3) A(n+2) A(n+1)| |A(n+1) A(n) A(n-1)|*|1 0 1|=|A(n+2) A(n+1) A(n) | | A(n) A(n-1) A(n-2)| |1 0 0| |A(n+1) A(n) A(n-1)|`

which means:

`|A(5) A(4) A(3)| |1 1 0|^n |A(n+5) A(n+4) A(n+3)| |A(4) A(3) A(2)|*|1 0 1| =|A(n+4) A(n+3) A(n+2)| |A(3) A(2) A(1)| |1 0 0| |A(n+3) A(n+2) A(n+1)|`

This means we can find expressions for A(2n) and A(2n + 1) in terms of A(n) (and parameters close to n). So a logN solution is possible using this approach.

Of course, none of this is required to solve this problem because the constraints are very limited. I just gave it more thought because science.

FutureGadgetLab + 0 comments *Nice*abhijeet1403 + 0 comments You sir, Are Awesome !

aod7br + 0 comments Nice approach. Did you develop it yet and reached an analitical solution?

aod7br + 0 comments [deleted]riyagayasen + 0 comments Genius!

pjoscely + 0 comments Perhaps you could diagonalize your matrix via eigenvalues to come up with an analytical solution. This if I recall works for Fib #s, should work here also.

valipour + 2 comments Just to add, for further simplicity, you can consider:

`A[0] = 1`

-- there is 1 way to climb zero stairs- for any
`ix < 0`

:`A[ix] = 0`

- for any
`ix > 0`

:`A[ix] = A[ix-3] + A[ix-2] + A[ix-1]`

arkenibrahim + 1 comment im pretty sure there are 0 ways to climb 0 stairs.

Freak_1231 + 1 comment no...an empty set is still a set....so there is 1 way you can climb 0 stairs...ie 0! (zero factorial) =1

condrint + 1 comment yes but an empty set's cardinality is 0. however, i dont know if the analogy still fits...

mrey98 + 0 comments This case, A(0) goes beyond Software Development and it's a question that humans have tried to answer since the beginning of times trying to understand the nature of reality. "When there's nothing, is there still something? " i.e "Before the universe was created, was there something already there?"

AdamBalint + 0 comments According to the rules that were stated, you can always assume one staircase and one stair as the minimum

rozcietrzewiacz + 1 comment Hey!

`|1 1 0| |1 0 1| |1 0 0|`

now THAT's a GLIDER!

So you truly hacked it, man.

vernisan + 0 comments I found this article very helpful for explaining the general case of solving linear recurrences with matrix exponentiation, and why a logN solution can be achieved: http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

JimNero009 + 0 comments Never thought of the problem like this before. It all seems so obvious and simple now. Good work!

chickoo_1 + 0 comments I implemented this concept using matrix exponentiation ,here goes the code :))

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class Solution { public static class Matrix{ static int n; public Matrix(int n) { this.n=n; } static long[][] multiply(long[][] a ,long[][] b) { long[][] ans=new long[n][n]; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ ans[i][j]=0; for(int k=0;k<n;k++) ans[i][j]+=a[i][k]*b[k][j]; } return ans; } static void print(long[][] a) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) System.out.print(a[i][j]+" "); System.out.println(); } } //Matrix Exponentiation static long MatrixExpo(long[][] base ,int power ) { // print(base); //base cases if(power<=0) return 0; if(power==1) return 1; if(power==2) return 2; if(power==3) return 4; power-=3; long[][] ans=new long[n][n]; //Make Answer-matrix for(int i=1;i<n;i++) for(int j=0;j<n;j++) ans[i][j]=0; ans[0][0]=4;ans[0][1]=2;ans[0][2]=1; //Left-handside matrix //4 2 1 //0 0 0 //0 0 0 while(power>0) { if(power%2==1) ans=multiply(ans ,base); power=power/2; base=multiply(base ,base); } //return final answer F(n) return ans[0][0]; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int s = in.nextInt(); long[][] m=new long[3][3]; //1 1 0 //1 0 1 //1 0 0 m[0][0]=m[1][0]=m[2][0]=1;m[0][1]=1;m[0][2]=0; m[1][1]=0;m[1][2]=1;m[2][1]=0;m[2][2]=0; for(int a0 = 0; a0 < s; a0++){ int n = in.nextInt(); Matrix mat= new Matrix(3); System.out.println(Matrix.MatrixExpo(m ,n)); } } }

DannyBwoy + 1 comment Insane The java code for the same is as follows:

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static int[][] mul(int [][] a){ int b[][] = {{1,1,0},{1,0,1},{1,0,0}}; int c[][] = {{0,0,0},{0,0,0},{0,0,0}}; for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) c[i][j] +=a[i][k]*b[k][j]; return c; } public static int s(int n){ int a[][] = {{1,1,0},{1,0,1},{1,0,0}}; if(n==1) return 1; else if(n==2) return 2; else if(n==3) return 4; else {for(int i=0;i<n-2;i++) a = mul(a); return 4*a[0][2] +2*a[1][2] +a[2][2] ;} } public static void main(String[] args) { Scanner in = new Scanner(System.in); int s = in.nextInt(); for(int a0 = 0; a0 < s; a0++){ int n = in.nextInt(); System.out.println(s(n)); } } }

chickoo_1 + 0 comments This is probably not matrix exponentiation , the complexity is linear

Freak_1231 + 0 comments [deleted]mike_littlewd + 0 comments Can I get an explanation as to where the matrix comes from here?

andadeacu + 0 comments How did you deduce the formula?

d_satheesh22 + 1 comment [deleted]alaniane + 0 comments It's not all of the values leading up to six, so 24, 42, 6, 15, 51, 114, 141, and 411 are not valid. You can only use the digits 1,2,3 to form the number 6. I am not going to list out all of the combinations, but if you do it by hand, you will find that there are only 24.

VladimirS + 0 comments Nice observation. Only one note: Matrix by matrix multiplication unnecessary, you can use vector by matrix:

alex_daymon + 4 comments Java linear solution:

public static int calcWays(int n) { if (n < 1) return 0; if (n == 1) return 1; if (n == 2) return 2; if (n == 3) return 4; int[] ways = new int[] {1,2,4}; for (int i = 4; i < n; i++) { int idx = (i - 1) % 3; ways[idx] = ways[0] + ways[1] + ways[2]; } return ways[0] + ways[1] + ways[2]; }

pradyumnameena + 1 comment i did the same but was unable to pass test case 5,6,7,8

hvdijk + 0 comments I also failed to pass those test cases until I noticed the contradiction in the challenge: the challenge both says to calculate the result modulo 10^9+7 and to calculate the result modulo 10000000007 (aka 10^10+7). I had the first; the last is what the test cases need.

almostcolin + 0 comments This still calculates from i=4 to n each time. Could make this linear by making "ways" global to store previously found values and only running recursion if you don't have ways[n] yet.

pooja_b25 + 0 comments [deleted]woldegebrielkeb1 + 1 comment here is another java solution using dynammic programming

static int stepPerms(int n) { if(n==1) { return 1; } int[] m = new int[n+1]; m[0] = 1; return helper(n,m); } private static int helper(int n, int[] m) { if(n<0) { return 0; } if(m[n]!=0) { return m[n]; } if(n==1) { return 1; } m[n] = helper(n-3,m) + helper(n-2,m) + helper(n-1,m); return m[n]; }

amanindersinghk1 + 0 comments can anyone explain this solution. why ,(n-3,m) + helper(n-2,m) + helper(n-1,m).....?

writerphone + 0 comments impressive!

metazilla + 0 comments Here's an analytical solution in Python:

import os a = ((19+3*33**(1/2))**(1/3) + (19-3*33**(1/2))**(1/3) + 1)/3 c = (a - 1)/(4*a - 6) trib = lambda n: int(round(c * (a ** n))) if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') s = int(input()) for s_itr in range(s): n = int(input()) res = trib(n) fptr.write(str(res) + '\n') fptr.close()

How it works:

It is well known that fibonacci numbers can be calculated in O(log n) time using matrix exponentiation, similarly, tribonacci numbers can be found using: T = [[0, 1, 0], [0, 0, 1], [1, 1, 1]], the transformation matrix such that T*F_i = F_i+1 where F is [f(i-3), f(i-2), f(i-1)] The variable a in my solution is also known as the tribonacci constant, and is the only eigenvalue of T that is positive and real. (The other two eigenvalues have complex parts.)

As shown in Dresden 2014 (http://emis.ams.org/journals/JIS/VOL17/Dresden/dresden6.pdf), for 'large enough' values of n (in this case, n>=-1), you can throw away the terms depending on the complex eigenvalues, leaving us with this equation (after simplifying): F_n = rnd((a-1 / 4a-6) * a^n-1)

A note on precision: The results returned here are only accurate up to n=52 because of the limitations of Python floats. This can be improved by using the built in Decimal class and setting a higher precision.

And a note on speed: There are differences in **, pow, and math.pow for exponentiation. According to the answer here (https://stackoverflow.com/a/48848512), math.pow is O(1) time while ** and pow are O(log n), but some tests with timeit show that ** gives the best performance with small n values.

andikadevs + 0 comments cool algorithm

modhura3797 + 2 comments approach is very nice. I tried to implement your approach same as you mentioned.

def stepPerms(n): if (n == 1): return 1 elif (n == 2): return 2 elif (n == 3): return 4 else: return (stepPerms(n-1) + stepPerms(n-2) + stepPerms(n-3)) % 10000000007

but it is getting TLE for test case 5 to 8. So what's the way to solve this?

oybekjon + 0 comments you have to use memoization

chepurivishwam10 + 0 comments # define MOD 10000000007

int stepPerms(int n) {

`vector<int> dp= {1,1,2,4}; for(int i=4;i<n+1;i++){ dp.push_back((dp[i-3]%MOD + dp[i-2]%MOD +dp[i-1]%MOD)%MOD); } return dp[n];`

}

using bottom up approach

Abe10 + 0 comments yeah science!!

cris_kgl + 0 comments # Java solution

### PASSES 100% OF TEST CASES ✅

### O(N) TIME COMPLEXITY

### O(1) SPACE COMPLEXITY

Dude... just memoize as it is done in optimizing a classic Fibo problem! 😁

static int stepPerms(int n, Map<Integer, Integer> map){ if(n == 1) return 1; if(n == 2) return 2; if(n == 3) return 4; if(map.containsKey(n)) return map.get(n); int res = 0; res += stepPerms(n - 1, map); res += stepPerms(n - 2, map); res += stepPerms(n - 3, map); map.put(n, res); return res; }

Note that we need to pass a hashmap before calling the function in the loop for each staircase.

I created this simple diagram for you to see the idea more clearly if you had any questions 😉

# Number of ways to climb a staircase

### possible jumps are 1 2 3 stairs

Important to notice that A(n) = A(n-3) + A(n-2) + A(n-1) being

.*A(n) the NUMBER OF WAYS to clib a staircase of n stairs*Let's see why this series approach works with an example:

Imagine we are trying to compute 4 from 3, 2 & 1.

When we sum we are saying basically that there are 3+2+1 ways to end up in a step of the staircase that is in a one step reachable distance to the step we are trying to reach in this case step of height 4.

- We can jump from step 1 with a jump of distance 3 to get to 4. Since there is only one combination to get to staircase 1,
**this adds up only 1 to our final result** - We can jump from step 2 with a jump of 2 to get to 4 . There are 2 ways to get to step 2 so
**it adds up 2 to the final result** - We can jump from step 3 with a jump of 1 to get to 4. There are 4 ways to get to step 3 so
**it adds up 4 to the final result**

- We can jump from step 1 with a jump of distance 3 to get to 4. Since there is only one combination to get to staircase 1,

shiyanch + 11 comments You can use recursion to solve this problem with a cache.

private static Map<Integer, Integer> map = new HashMap<>(); public static void main(String[] args) { Scanner in = new Scanner(System.in); int s = in.nextInt(); for(int a0 = 0; a0 < s; a0++){ int n = in.nextInt(); System.out.println(climb(n)); } } private static int climb(int n) { if(n < 0) return 0; if(n == 0) return 1; if(!map.containsKey(n)) { int count = climb(n-1) + climb(n-2) + climb(n-3); map.put(n, count); } return map.get(n); }

despart + 0 comments I did the same but I cached the 3 recursions everytime... sigh

javaboy_99 + 0 comments [deleted]Shivang_dhuria + 0 comments give input 1 30 your code will crash!

rkennedysurf + 1 comment Same solution in PyPy3! Speed up was enough to pass all cases but python3 is still too slow. Idea is to check if you have already calculated value for n, and if not then to add it to the dictionary.

seen = {0: 1} def combine(n): if n < 0: return 0 if n in seen: return seen[n] ret = combine(n - 1) ret += combine(n - 2) ret += combine(n - 3) seen[n] = ret return ret

nishkalavallabhi + 0 comments That was useful @adding stuff to dictionary.

jeotte + 0 comments I totally did the same thing.

daniele_strollo + 1 comment Did a similar python approach

steps=[1,2,3] cache={} def climb(n): global cache leaves=0 if n < 0: return for s in steps: if n - s >= 0: if cache.has_key(n-s): subres=cache[(n-s)] else: subres=climb(n - s) cache[(n - s)] = subres leaves+=subres if n - s == 0: leaves += 1 return leaves

and climb(240) returns 2028382748046767387253483395022331055100978649577557465746184401

with no pain at all ;)

GeoMatt22 + 0 comments You can also use the @functools.lru_cache() decorator.

mininin222 + 0 comments Worked like a charm in Python3! No problem with big numbers too.

dict = {0:0, 1:1, 2:2, 3:4} def steps(n): if n in dict.keys(): return dict.get(n) result = steps(n-3) + steps(n-2) + steps(n-1) dict.update({n: result}) return dict.get(n)

JChiquin + 1 comment I also did it like yours

#include <vector> #include <iostream> using namespace std; vector<int> W(37,0); int f(int n){ return W[n] ? W[n] : W[n] = n>=3 ? f(n-3)+f(n-2)+f(n-1) : (n>>1)+1; } int main() { int n;cin>>n; //ignoring s while(cin>>n and cout<<f(n)<<endl); return 0; }

harishmakm1997 + 1 comment could you please explain you code??

JChiquin + 2 comments My solution uses recursion and memoization (Dynamic Programming). It's more readable if you see it this way:

#include <vector> #include <iostream> using namespace std; vector<int> W(37,0); int f(int n){ if(W[n]!=0) //It had already been calculated return W[n]; else{ if(n>=3) W[n]=f(n-3)+f(n-2)+f(n-1); else if(n==1 or n==2) W[n]=n; else //n == 0 W[n]=1; //these last two are this: (n>>1)+1 } return W[n]; } int main() { int n;cin>>n; //ignoring s while(cin>>n and cout<<f(n)<<endl); //Here I read and write until the whole input stream has been read return 0; }

Sorry my english

Lalchetaketan022 + 0 comments Thank you for your detailed explanation.

I got your entire DP code. Only one doubt I have and it is related to ways to calculate 3 steped staircase.

Code says it is w[3] = w[0]+w[1]+2[2]=0+1+2=3 where as one can climb it with four different combinations.. Here it is 1 (1+1+1), 2 as (1+2), 3 as (2+1) and fourth as (3) all 3 steps in a go.

Am i missing something?

sharmakalrav74 + 0 comments [deleted]

htfonseca + 0 comments A simple version to your code:

`private static int stepPerms(int n) { if(n < 0) return 0; if(n == 0) return 1; return map.computeIfAbsent(n, key -> stepPerms(key-1) + stepPerms(key-2) + stepPerms(key-3)); }`

nikolovski23 + 0 comments Niiiiiice! The map fixed my termination due to timeout!

pooja_b25 + 1 comment I am not able to understand this solution. Can you please explain?

nikolovski23 + 0 comments Check out memoization and dynamic programming: https://www.youtube.com/watch?v=P8Xa2BitN3I

jdc219 + 1 comment Java DP solution, no recursion needed. Runtime O(n)

public static int calcNum(int n) { int[] array = new int[n]; if (n == 1) { return 1; } else if(n == 2) { return 2; } else if(n == 3) { return 4; } array[0] = 1; array[1] = 2; array[2] = 4; for (int i = 3; i < n; i++) { array[i] = array[i-1] + array[i-2] + array[i-3]; } return array[array.length-1]; }

abgcmu + 3 comments clever! a slight modification would be to use

`new int[3]`

This gives us (O(1) space) and in the for loop you can replacearray[i] = array[i-1] + array[i-2] + array[i-3];

with

array[i % 3] = array[0] + array[1] + array[2];

to remain within bounds and return the value eventually.

Pratik95 + 1 comment please can you explain why %3 and not any other. Also please explain logic

pgeadas + 0 comments Because the next step only depends on the 3 previous steps, you can use a circular buffer of lenght 3, hence the "mod 3". So even for an arbitrary big value of n, you will never get out of memory by allocating a huge array.

So, for a n = 4, the array[0] would be ignored, for a n = 5, array[0] and array[1], etc... abgcmu solution just reuses the unused positions of the array.

Hope that helped.

Watercycle + 0 comments Thank you for this insight, there's so many nifty uses for the modulus operator :)

basant1431k + 0 comments Nice one but you need to change one more thing int j = 0; for (int i = 3; i < n; i++) { array[i%3] = array[0] + array[1] + array[2]; j = i%3; } //return array[array.length-1]; place of this return below

`return array[j];`

gleb_i_nikonorov + 1 comment FYI: It seems like the problem specification is broken. It said to return the number of ways to climb the stairs modulo

`10^9 + 7`

. It seems like they really wanted to say`10^10 + 7`

based on examples and accepted answers for problem.karim_safin + 0 comments Same here. If you just delete your "modulo logic" and let it freely overflow, you'll get "Accepted". Very annoying.

miljanm + 2 comments O(n) Python solution to get nth number in the modified fibonacci sequence.

def get_mod_fib(n): f1, f2, f3 = 1, 2, 4 for i in xrange(n-1): f1, f2, f3 = f2, f3, f1 + f2 + f3 return f1

Freak_1231 + 0 comments [deleted]rajeshgupta88 + 1 comment Could anybody please explain??

gracetian6 + 0 comments We first create a tuple f1, f2, f3 and assign it the values for stepPerms(1), stepPerms(2), and stepPerms(3) respectively. For reference, stepPerms(n) is the number of ways to climb a staircase of height n. Note that stepPerms(n) = stepPerms(n-1)+stepPerms(n-2)+stepPerms(n-3).

We then iterate n-1 times. The first iteration gives us a tuple of stepPerms(2), stepPerms(3), stepPerms(4). The 2nd iteration gives us the tuple stepPerms(3), stepPerms(4), stepPerms(5). Following this process, the ith iteration gives us the tuple stepPerms(i), stepPerms(i+1), stepPerms(i+2). Hence, the final (n-1)th iteration gives us stepPerms(n), stepPerms(n+1), stepPerms(n+2). The first number in that tuple, stepPerms(n) is our desired answer.

This is a clever solution since we are only calculating # of ways for each integer once, and simply shifting these values and building off of it!

TeachLeadDevelop + 3 comments So full blown memonization will definantly work. However, we know that we only need a memory of three for our formula. One space efficient implementation method is a circular buffer.

def climbing_patterns(n): positions = [0,0,1] for s in xrange(n): positions[s % 3] = sum(positions) return positions[s % 3]

bhrgunatha + 1 comment No need for a buffer even, just 3 variables and extend the well-known method for calculating fibonacci numbers.

`def paths(n): s0, s1, s2 = 1, 1, 2 for _ in range(n): s0, s1, s2 = s1, s2, s0 + s1 + s2 return s0`

aod7br + 1 comment Simple and elegant, but still O(N*V) on the VALUE of the input, could be slow for large Vs

bhrgunatha + 0 comments When you say O(N*V) does V represent the overhead of storing/manipulating very large numbers?

If

**yes**, then I don't think it's useful for analysing runtime behaviour for this exercise because:1) It's uses python's builtin handling of numbers.

2) Every other solution will have the same overhead and so I think can be treated as a constant factor.

I'm very interested to learn what is faster for large Vs?

I like goodengineer's analysis to get O(log n) - which is equivalent (I think) to the SICP 1.19 exercise on fibonacci numbers

If

**no**, then what does V represent?

Pratik95 + 1 comment Please can you explain why %3 and not other number. please tell the logic

arkenibrahim + 0 comments Because we only care about the last 3 elements.

harshal_2894 + 0 comments Could you explin how would this code get the number of patterns that are possible for climbing?

simon_livesey + 3 comments You only need to remember the last 3 values so just store them in an int[] and update until you are done - C# code:

`static int steps(int n) { int[] arr = {1,2,4}; if (n < 4) return arr[n - 1]; for (int i = 5; i <= n; i++){ arr[(i + 1) % 3] = arr[0] + arr[1] + arr[2]; } return arr[0] + arr[1] + arr[2]; }`

hennovanrensburg + 0 comments Excellent!

mikemiksch + 1 comment In this solution, how would we handle n = 4?

cgarvin + 0 comments The loop would be skipped, and it would return 7

JamesCater + 0 comments Nice... can be simplified a touch more

`public static int stepPerms(int n) { int[] arr = { 1, 2, 4 }; for (int i = 4; i <= n; i++) { arr[(i - 1) % 3] = arr.Sum(); } return arr[(n - 1) % 3]; }`

an_shuman777 + 1 comment Recursion with memoization, Here is my CPP code :

const int MAX = 50; int dp[MAX]; int rec(int n){ if(n==1){return dp[1]=1;} else if(n==2){return dp[2]=2;} else if(n==3){return dp[3]=4;} else if(dp[n]!=0){return dp[n];} else {return dp[n]=rec(n-1)+rec(n-2)+rec(n-3);} }

sahilgoyal31 + 0 comments thankx

zoomis_gogo + 2 comments This is my Python2 code which I've used a memory.

memory = {1:1, 2:2, 3:4} def num_ways(n): if not n in memory.keys(): memory[n] = num_ways(n-1) + num_ways(n-2) + num_ways(n-3) return memory[n]

metagordon + 2 comments can you explain please the use of .keys()

zoomis_gogo + 0 comments I just used it to get all keys in the dictionary in order to check if there is a key in the dictionary.

cgarvin + 0 comments He could have just said

if n not in memory

cz772 + 0 comments I used the same cache dictionary like you did but timed out... only iterative approach passed all the test for me... weird.

jonny_mcallister + 0 comments If you are having some trouble and want a hint without getting the answer from this dicussion:

- Consider instead a 2 operation case (Davis can go up 1, or 2 steps at a time). In this case we see that all ways to n-2 result in the same total if the next op is 2. And all ways to n-1 result in the same total if the next op is 1.
- From the n-2 stair, an op of 1 gets Davis to the n-1 stair, so it will be counted as an n-1 way.

There are various ways to code the solution. You do not

*need*DP or recurrsion, but this is the most straight forward way.Here is a good reference: http://ms.appliedprobability.org/data/files/Articles%2047/47-1-4.pdf

Sort 259 Discussions, By:

Please Login in order to post a comment