Did I do not understand climbing stairs right or the common answer is wrong?


  • 0
    C

    Currently, the answer to this question is f(n)=f(n-1)+f(n-2); It is kind like this

    1-1
    2-2
    3-3
    4-5
    5-8
    6-13
    

    But I just do not feel it right. For example, for 6 steps there are only 12 different ways not 13:

    0x 2: 
    111111
    1x2:  
    21111
    12111
    11211
    11121
    11112
    2*2:
    2211
    2121
    2112
    1212
    1122
    3*2:
    222
    

    Do I miss anything or it is truly 12?

    Anyway, based on the math I have, the code should be as following:

    public class Solution {
        public int climbStairs(int n) {
            if(n==1||n==2)
                return n;
            else{
                int m=n/2;
                int result=1;
                for(int i=1;i<=m;i++){
                    result+=(n-2*i)*i+1;
                }
             return result;   
            }
        }
    }

  • 0
    A

    Take a look at of 2*2 part,I think the follow one should be there: 1221.


  • 0
    D

    I think you missed the 1221. you can used the coding way to list all of the solution. at fist climbing 2 steps, second climbing 1:

    2 2 2
    2 2 1 1
    2 1 2 1
    2 1 1 2
    2 1 1 1 1
    1 2 2 1
    1 2 1 2
    1 2 1 1 1
    1 1 2 2
    1 1 2 1 1
    1 1 1 2 1  
    1 1 1 1 2
    1 1 1 1 1 1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.