Skip to content

Problem 4: Climb Stairs (200pts)

Problem

Nolan lives on the sixth floor of the dormitory building and feels frustrated about climbing such a long flight of stairs every day. He is wondering how many different ways he can go up the stairs. He knows that going up the stairs requires n steps, where n is a positive integer, and he can either take 1 or 2 steps each time.

Please help him write a function count_stair_ways which takes in the total steps n and returns the number of ways to climb up a flight of n stairs.

Nolan 住在宿舍楼的六楼，每天爬这么长的楼梯让他感到沮丧。他想知道他爬楼梯有多少种不同的方式。他知道爬楼梯需要 n 级台阶，其中 n 是一个正整数，他每次可以走 1 级或 2 级台阶。

请帮助他编写一个函数 count_stair_ways，该函数接受总台阶数 n，并返回爬完 n 级楼梯的方法数。

def count_stair_ways(n):
    """Returns the number of ways to climb up a flight of
    n stairs, moving either 1 step or 2 steps at a time.
    >>> count_stair_ways(3)
    3
    >>> count_stair_ways(4)
    5
    >>> count_stair_ways(10)
    89
    """
    "*** YOUR CODE HERE ***"

Nolan realized that he could take more steps at a time! Now he is able to take up to and including k steps at a time, where k is a positive integer.

Write a function count_k that takes in the total steps n and maximum steps k at a time, then return the number of ways to climb up a flight of n stairs. (k may be larger than n)

Nolan 意识到他一次可以迈更多的步子！现在他一次最多可以迈 k 级台阶（包括 k 级），其中 k 是一个正整数。

编写一个函数 count_k，它接受总台阶数 n 和一次最多迈的台阶数 k，然后返回爬完 n 级楼梯的方法数。（k 可能大于 n）

def count_k(n, k):
    """Counts the number of paths to climb up a flight of n stairs,
    taking up to and including k steps at a time.
    >>> count_k(3, 3) # 3, 2 + 1, 1 + 2, 1 + 1 + 1
    4
    >>> count_k(4, 4)
    8
    >>> count_k(10, 3)
    274
    >>> count_k(300, 1) # Only one step at a time
    1
    >>> count_k(3, 5) # Take no more than 3 steps
    4
    """
    "*** YOUR CODE HERE ***"

Hints

Hint: Your solution for count_k will follow a very similar logic to what you did in count_stair_ways.

  • 你对 count_k 的解决方案将遵循与你在 count_stair_ways 中所做的非常相似的逻辑。

  • 这类题在高中应该很常见，可以回想一下如何实现。

  • 注意 count_k 函数中的 doctests，先找 base case，然后尝试递推。

Solutions

对于 count_stair_ways(n)，考虑 Nolan 爬楼梯的最后一步，他可能走 1 级或 2 级台阶。

走 1 级台阶时， Nolan 先爬了 n - 1 级台阶；走 2 级台阶时， Nolan 先爬了 n - 2 级台阶。

如果我们把爬 n - 1 级台阶和爬 n - 2 级台阶的方法数加起来，那么就是爬 n 级台阶的方法数。

注意 base case：当 n <= 2 时 count_stair_ways(n) 恰好等于 n

def count_stair_ways(n):
    if n <= 2:
        return n
    else:
        return count_stair_ways(n - 1) + count_stair_ways(n - 2)

对于 count_k(n, k)，同样的，我们应该把爬 n - 1 级台阶、爬 n - 2 级台阶……爬 n - k 级台阶的方法数加起来。

注意 base case：根据 doctests，我们会发现当 n <= k 时 count_k(n, k) 的返回值恰好为 \(2^{n-1}\)，据此：

def count_k(n, k):
    if n <= k:
        return 2 ** (n - 1)
    else:
        result = 0
        i = 1
        while i <= k:
            result += count_k(n - i, k)
            i += 1
        return result

压行

def count_stair_ways(n):
    return n if n <= 2 else count_stair_ways(n - 1) + count_stair_ways(n - 2)

def count_k(n, k):
    return 2 ** (n - 1) if n <= k else sum([count_k(n - i, k) for i in range(1, k + 1)])

计算前缀和，复杂度 \(O(n)\) 

def count_k(n, k):
    dp = [1, 1]
    s = [1, 2]
    for i in range(2, n+1):
        num = 0
        if(i <= k): num = s[i-1]
        else: num = s[i-1] - s[i-k-1]
        dp.append(num)
        s.append(num + s[i-1])
    return dp[n]