python假设一段楼梯共n个台阶，小明一步最多能上3个台阶（当然也可以走一个或者两个台阶），小明上这段楼梯一共有多少种方法? 例如：n=5时，得到(1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 1), (1, 1, 3), (1, 2, 1, 1), (1, 2, 2), (1, 3, 1), (2, 1, 1, 1), (2, 1, 2), (2, 2, 1), (2, 3), (3, 1, 1), (3, 2) 共 13种方法。

这是一个典型的动态规划问题。可以使用递归或者迭代方式实现。以下是迭代方式的代码实现：

def count_ways(n):
    if n <= 2:
        return n
    elif n == 3:
        return 4
    else:
        dp = [0] * (n + 1)
        dp[1], dp[2], dp[3] = 1, 2, 4
        for i in range(4, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        return dp[n]

其中，dp数组表示走到第i个台阶的方法数，dp[1]=1，dp[2]=2，dp[3]=4。从第4个台阶开始，每次可以从i-1、i-2或i-3的台阶上走上来，所以状态转移方程为：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。最后返回dp[n]即可。

可以使用如下代码进行测试：

n = 5
print(count_ways(n))  # 输出13

相关问题

python假设一段楼梯共 15 个台阶，小明一步最多能上 3 个台阶。编写程序计算小明上这段楼 梯一共有多少种方法。要求给出递推法和递归法两种代码

递推法代码：

def climbStairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
    dp = [0] * (n+1)
    dp[1], dp[2], dp[3] = 1, 2, 4
    for i in range(4, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    return dp[n]

print(climbStairs(15))

递归法代码：

def climbStairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
    return climbStairs(n-1) + climbStairs(n-2) + climbStairs(n-3)

print(climbStairs(15))

这两种方法的时间复杂度都是O(n)，其中递推法是自底向上的动态规划，递归法是自顶向下的动态规划。

假设一段楼梯共15个台阶，小明一步最多能上3个台阶，分别用递推和递归算法求方法数python

假设你要用递推和递归算法解决这个问题，你可以创建一个函数来计算从0到指定台阶数的所有可行走法。这里我将提供一个简单的Python解决方案：

**递推法（动态规划）**:

def step_count(n):
    # 创建一个列表来存储之前的结果
    dp = [0] * (n + 1)
    
    # 初始化基本情况，即0阶台阶只能有一种走法（不走）
    dp[0] = 1
    
    # 递推公式：对于每个台阶，可以是一个单独上三个台阶，或者之前走过的任意台阶数加一
    for i in range(1, n+1):
        if i >= 3:
            dp[i] += dp[i - 3]
        else:
            dp[i] = dp[i - 1]   # 如果只走了一个台阶

    return dp[n]

# 调用函数计算15级台阶的方法数
steps_to_15 = step_count(15)

**递归法**:

def recursive_steps(n, current=0):
    # 基本情况：当达到目标台阶数，返回1（一种走法）
    if n == 0:
        return 1
    elif n < 0 or current > n:   # 边界条件或越界，则返回0
        return 0
    else:
        # 每次递归都包括当前一步和其他剩余台阶的组合
        return recursive_steps(n - 1, current + 1) + recursive_steps(n, current)

steps_to_15_recursive = recursive_steps(15)

这两个函数都会返回15级台阶的小明可以到达的步数。