Important induction thinking behind this question


  • 1
    W
    int climbStairs(int n) {
            if(n==0)    return 0;
            int i = 1;
            int end_2 = 0;
            int end_1 = 1;
            while(i < n){
                int tmp = end_1;
                end_1 = end_2 + end_1;
                end_2 = tmp;
                i++;
            }
            return (end_1+end_2);
        }
    

    The idea of my algorithm is based on induction thinking. Every combination ending with 1 will induct to one combination end with 2 and one combination end with 1.

    For example, 1211 will become 12111 and 1212.

    Hence, in my code, I will count the number of combinations ending with 1 and 2, then the code will make the induction from the previous combination to get the next level result.


Log in to reply
 

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