We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Recursion: Davis' Staircase
You are viewing a single comment's thread. Return to all 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!