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

### 回答1：
递推法代码：

n = 15
dp = [] * (n+1)
dp[] = 1
for i in range(1, n+1):
    for j in range(1, 4):
        if i >= j:
            dp[i] += dp[i-j]
print(dp[n])

递归法代码：

def climb_stairs(n):
    if n == :
        return 1
    if n < :
        return 
    return climb_stairs(n-1) + climb_stairs(n-2) + climb_stairs(n-3)

print(climb_stairs(15))

### 回答2：
递推法：

假设第 $i$ 个台阶的上法的数量为 $dp_i$，则有：

$$ dp_i = dp_{i-1} + dp_{i-2} + dp_{i-3} $$

其中，当 $i \le 3$ 时，有特殊情况需要考虑。

递推的初始值为 $dp_1=1,dp_2=2,dp_3=4$。

接下来，我们可以写出完整的代码：

n = 15
dp = [0] * 16
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]
print(dp[n])

递归法：

本题也可以使用递归的方法进行求解，对于这种方法，我们需要注意的是，递归树的深度可能会非常深，导致程序运行缓慢或甚至超时。因此，我们可能需要使用备忘录或动态规划方法来优化程序。

对于本题，我们首先需要编写递归函数，代码如下：

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

接下来，我们可以调用这个函数来计算 $n=15$ 时的答案：

print(climb(15))

需要注意的是，如果不进行优化，这种方法很容易超时，因此在实际使用中，我们需要根据具体情况进行程序的优化。

### 回答3：
递推法的程序如下：

n = 15  # 楼梯总台阶数
step = 3  # 小明最多能上的台阶数

dp = [0] * (n + 1)  # 初始化动态规划数组
dp[0] = 1  # 初始状态

for i in range(1, n + 1):  # 递推计算
    for j in range(1, step + 1):
        if i - j >= 0:
            dp[i] += dp[i - j]

print(dp[n])  # 输出结果

解释：采用动态规划，定义一个长度为 n+1 的数组 dp，其中 dp[i] 表示走完 i 个台阶的方法数目。状态转移方程为 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，因为小明一步最多上 3 个台阶，所以可以从 i-1、i-2、i-3 三个状态转移过来。最终 dp[n] 就是走完整段楼梯的方法数。

递归法的程序如下：

n = 15  # 楼梯总台阶数
step = 3  # 小明最多能上的台阶数

def climb(n):
    if n < 0:  # 边界条件1
        return 0
    elif n == 0:  # 边界条件2
        return 1
    else:
        return climb(n-1) + climb(n-2) + climb(n-3)

print(climb(n))  # 输出结果

解释：采用递归的思路，定义一个名为 climb 的函数，其中 climb(n) 表示走完 n 个台阶的方法数目。递归终止条件有两个：当台阶数 n 小于 0 时返回 0，当台阶数 n 等于 0 时返回 1。针对状态转移方程 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，采用递归方式进行计算。最终 climb(n) 就是走完整段楼梯的方法数。由于递归的深度可能很大，可能会造成栈溢出，因此递推法更常用。