数据结构 爬楼梯问题

爬楼梯问题是一个经典的动态规划问题。假设你要爬上n个台阶，每次只能爬1个或2个台阶。问有多少种不同的方法可以爬到楼顶。

解决这个问题可以使用动态规划的思想，定义一个数组dp，dp[i]表示爬到第i个台阶的方法数。根据题目要求，爬到第i个台阶有两种方式：从第i-1个台阶爬1个台阶，或者从第i-2个台阶爬2个台阶。因此，可以得到状态转移方程：dp[i] = dp[i-1] + dp[i-2]。

初始化dp数组，dp[0]=1表示爬到第0个台阶的方法数为1，dp[1]=1表示爬到第1个台阶的方法数为1。然后从第2个台阶开始计算dp[i]，直到计算到第n个台阶为止。最后返回dp[n]即为所求的方法数。

下面是使用Python实现的代码示例：

def climbStairs(n):
    if n == 0 or n == 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

通过调用`climbStairs(n)`函数，传入楼梯的总数n，即可得到爬到楼顶的不同方法数。

相关问题

爬楼梯问题c

好的，爬楼梯问题是经典的动态规划问题，题目描述为：假设你正在爬楼梯，楼梯有 n 阶台阶，每次你可以爬 1 阶或 2 阶，那么你有多少种不同的方法可以爬到楼梯顶部？

解题思路：这是一道典型的动态规划问题，我们可以用 dp[i] 表示爬到第 i 阶楼梯的不同方法数，根据题目要求，到达第 i 阶楼梯有两种方法：从第 i-1 阶楼梯爬一阶或从第 i-2 阶楼梯爬两阶。因此，dp[i] = dp[i-1] + dp[i-2]，边界条件为 dp[0] = 1，dp[1] = 1。最终答案为 dp[n]。

以下是 C++ 代码实现：

int climbStairs(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for(int i=2; i<=n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

爬楼梯问题python

爬楼梯问题是一个经典的动态规划问题，可以用Python来求解。假设你要爬n级楼梯，每次可以爬1级或2级，那么有多少种不同的方法可以爬到楼顶呢？

我们可以使用递归或动态规划来解决这个问题。下面是使用动态规划的方法：

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

这个函数的参数是一个整数n，返回值是到达第n级楼梯的不同方法数。首先判断n是否等于1或2，如果是则直接返回1或2。创建一个长度为n+1的数组dp，dp[i]表示到达第i级楼梯的不同方法数。初始化dp[1]=1和dp[2]=2。然后从3开始遍历到n，每次计算dp[i]=dp[i-1]+dp[i-2]。最后返回dp[n]即可。

例如，如果n=3，那么dp数组的值为[0, 1, 2, 3]，最终结果为3。如果n=4，那么dp数组的值为[0, 1, 2, 3, 5]，最终结果为5。