You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Fibonacci
This question is a classic Fibonacci example.
What! You have never heard about Fibonacci Number?
However, you may have seen this picture.
If you scrutinize this picture carefully, you can find out some logic.
The two smaller numbers add up to the next number.
2 = 1+1
3 = 2+1
5 = 3+2
8 = 5+3
Isn’t that similar to the problem above?
Want to know more about Fibonacci Number definition ,here it is (wiki).
Solution
Let’s presume the solution function as Fn(n).
And let’s list out what we know.
n = 1,just have one way ➔ 1
n = 2,just two ways ➔ 1+1 or 2
Think about what will happen when n = 3
First, we only have two choices (one step or two steps). Is that right?
If we choose
one step ➔ two steps left
two steps ➔ one step left
When we know either one or two steps left, we know how many ways to go to the top.
So, we can write as
one step ➔ two steps left Fn(2)= 2
two steps ➔ one step left Fn(1)= 1
The answer of Fn(3) = Fn(2)+Fn(1) = 2+1 = 3
Next, let’s try n = 4
Same as above, we only have two choices (one step or two steps) at first
one step ➔ three steps left Fn(3) = 3 (the answer we have just gotten above)
two steps ➔ two steps left Fn(2) = 2
So, we can get the answer of Fn(4) = Fn(3)+Fn(2) = 3+2 = 5
Now, we can find out the rule of this problem.
Let’s try n as n for the last time
one step ➔ n-1 steps left Fn(n-1)
two steps ➔ n-2 steps left Fn(n-2)
⭐We can get the conclusion ➔ Fn(n) = Fn(n-1) + Fn(n-2)
Now, let’s turn the conclusion to simple programming language.
C# Solution
Solution1 (use the temporary interger)
public class Solution {
public int ClimbStairs(int n) {
//the first example has tell us how many distinct way for 1 or 2 steps stairs
int first = 1;
int second = 2;
int tmp = 0;
if(n<=2) //if n not more than 2 than just return the stpes it take
{
return n;
}
else
{
for(int i =3; i<=n;i++) //every iteration,will add the last two steps together and save as 'second'
{
tmp = second;
second+=first; //set second as now iteration needed steps
first = tmp; //set first as the last time needed steps
}
}
return second;
}
}
Solution2 (use the array to store)
public class Solution {
public int ClimbStairs(int n) {
if(n<2){
return n;
}
int[] ans = new int[n];
ans[0] = 1;
ans[1] = 2;
for(int i=2;i<n;i++) {
ans[i]=ans[i-1]+ans[i-2];
}
return ans[n-1];
}
}
Java Solution
Solution1 (use the temporary interger)
class Solution {
public int climbStairs(int n) {
if(n<2){
return n;
}
int first = 1;
int second = 2;
int tmp = 0;
for(int i =3; i<=n;i++) {
tmp = second;
second+=first;
first = tmp;
}
return second;
}
}
Solution2 (use the array to store)
class Solution {
public int climbStairs(int n) {
if(n<2){
return n;
}
int[] ans = new int[n];
ans[0] = 1;
ans[1] = 2;
for(int i=2;i<n;i++) {
ans[i]=ans[i-1]+ans[i-2];
}
return ans[n-1];
}
}
Python3 Solution
use list to store
class Solution:
def climbStairs(self, n: int) -> int:
if(n<2):
return n;
ans = [1,2];
for i in range(2, n):
ans.append(ans[i-1]+ans[i-2]);
return ans[n-1];
JavaScript Solution
use array to store
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let arr = [1,2];
for (var i = 2; i<n; i++) {
arr[i]=arr[i-1]+arr[i-2];
}
return arr[n-1];
};
Conclusion
🧡If my solution helps, that is my honor!
🧡You can support me by clicking some ad, Thanks a lot !
"You don't have to see the whole staircase, just take the first step."
Martin Luther King, Jr.
ai_front = {"insertion_before":"BEFORE","insertion_after":"AFTER","insertion_prepend":"PREPEND CONTENT","insertion_append":"APPEND CONTENT","insertion_replace_content":"REPLACE CONTENT","insertion_replace_element":"REPLACE ELEMENT","visible":"VISIBLE","hidden":"HIDDEN","fallback":"FALLBACK","automatically_placed":"Automatically placed by AdSense Auto ads code","cancel":"Cancel","use":"Use","add":"Add","parent":"Parent","cancel_element_selection":"Cancel element selection","select_parent_element":"Select parent element","css_selector":"CSS selector","use_current_selector":"Use current selector","element":"ELEMENT","path":"PATH","selector":"SELECTOR"};
Hi zyrastory.com administrator, Keep the good content coming!
Hi zyrastory.com admin, Keep up the great work!
Thanks a lot! We’re glad you’re enjoying zyrastory.com. If you ever have any suggestions or questions, feel free to let us know. We’re here to help!