爬楼梯，假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

**爬楼梯**

作为一个程序员，我经常遇到类似的问题：如何解决一个复杂的问题。爬楼梯是一个经典的例子，需要我们考虑如何一步步地达到目标。

假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次可以爬1、2 或3 个阶级。那么，我们该如何计算出爬完所有阶级所需的最少次数呢？

**动态规划**

这个问题可以使用动态规划来解决。动态规划是一种算法，通过分解一个复杂的问题成为多个子问题，然后逐步求解这些子问题，最终得到原问题的答案。

在本例中，我们定义一个数组 `dp`，其中 `dp[i]` 表示爬完前 i 个阶级所需的最少次数。我们可以根据以下规则填充这个数组：

* 如果 i =0，则 dp[0] =0，因为不需要爬任何阶级。
* 如果 i =1，则 dp[1] =1，因为只需要爬1 个阶级。
* 如果 i =2，则 dp[2] =2，因为可以直接爬2 个阶级。
* 对于 i >=3，我们有以下选择：
* 可以先爬1 个阶级，然后再爬剩下的 (i-1) 个阶级。因此，dp[i] = dp[i-1] +1。
* 也可以先爬2 个阶级，然后再爬剩下的 (i-2) 个阶级。因此，dp[i] = dp[i-2] +1。
* 最后，也可以先爬3 个阶级，然后再爬剩下的 (i-3) 个阶级。因此，dp[i] = dp[i-3] +1。

**代码实现**

def climbStairs(n):
 # 初始化动态规划数组 dp = [0]*(n+1)
 # 填充动态规划数组 for i in range(1, n+1):
 if i ==1:
 dp[i] =1 elif i ==2:
 dp[i] =2 else:
 dp[i] = min(dp[i-1], dp[i-2]) +1 # 返回爬完所有阶级所需的最少次数 return dp[n]

# 测试函数print(climbStairs(4)) # 输出:3