Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

topic:

Suppose you are climbing a staircase. It takes n steps for you to reach the top.

You can climb 1 or 2 steps at a time. How many different ways can you get to the top of the building?

Ideas:

I started by writing a function to calculate the number of people climbing the first and second floors, and then sorted and summed them, but it exceeded the range. Later I changed the range, but the result was wrong...

I don't know why.

Later I looked at the result and it looked more and more familiar. Isn't this the Fibonacci sequence?

It will be later

Result code:

​

int climbStairs(int n) {
    //int n,j;
    int sum=0;
    //scanf("%d",&n);
    int f_1=1;
    int f_2=2;
    int f_n=0;
    //int f_n_1=0;
    if(n==0||n==1||n==2)
    {
        return n;
    }
    for(int i=1;i<=n-2;i++)
    {
        f_n=f_1+f_2;
        //f_n_1=f_n+f_2;
        f_1=f_2;
        f_2=f_n;
    }
    return f_n;
   // return 0;
    
}

Keep up the good work!!!!!!!!!!!!!

Empty head.

If there is a better solution, please let me know, thank you!

Add a recursive method:

Recursive thinking:

The same as the Fibonacci sequence, that is, write Fibonacci recursively and finally output

See code:

int *func(int n,int* f_n,int f_1,int f_2)
{    
    --n;
    if(n == -1)
        return n;  
    f_n[n] = f_1+f_2;
    f_1 = f_2;
    f_2 = f_n[n];
    func(n,f_n,f_1,f_2); 
    return f_n;
}
​
int climbStairs(int n) {
    
    int f_n[n];
    func(n,f_n,0,1);
    return f_n[0];
}

I hope I am better today than I was yesterday!

Keep going!!