首页 > itarticle > PU Climbing Stairs

PU Climbing Stairs

admin 11月 12, 2020 0

Jan 01, 1970

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Given n will be a positive integer.

C Solution 1:

int climbStairs(int n) {
    if (n < 3) return n;
    int one_step_before = 2, two_step_before = 1;
    int i, res;
    for (i = 3; i <= n; i++) {
        res = one_step_before + two_step_before;
        two_step_before = one_step_before;
        one_step_before = res;
    }
    return res;
}

C Solution 2:

int climbStairs(int n) {
    int a = 0, b = 1;
    int i, res;
    for (i = 0; i < n; i++) {
        res = a + b;
        a = b;
        b = res;
    }
    return res;
}

Summary:

dp[n] = func(dp[n - 1], dp[n - 2], dp[n - 3],...)

LeetCode: 70. Climbing Stairs