# 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 + 1 comment can anyone explain this solution. why ,(n-3,m) + helper(n-2,m) + helper(n-1,m).....?

santaniabhimanyu + 0 comments It is because of recursion .if you see the recurrence equation is a(n)=a(n-1)+a(n-2)+a(n-3);so you need to find n-3,n-2,n-1 in order to get a(n).

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 + 1 comment # 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

psakshay16121997 + 0 comments hey im new here i can understand dp[i-3]+dp[i-2]+dp[i-1] but why are we taking %MOD

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!

Sort 285 Discussions, By:

Please Login in order to post a comment