一个人开始上楼梯，每次可以上一个台阶，也可以上两个台阶， 当他到达八个台阶时，有多少种走法，用java代码写出来

这是一个计算斐波那契数列的问题，可以用递归或动态规划来解决。

递归解法：

public int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
}

动态规划解法：

public int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int[] dp = new int[n+1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

当n为8时，输出结果为：

System.out.println(climbStairs(8)); // 34

相关问题

一个人爬楼梯，可以每次迈一个台阶，也可以每次迈两个台阶。输入要爬的台阶数，计算一共有多少种不同的走法。要求：递归实现

这个问题属于动态规划中的斐波那契数列问题，可以用递归的方式解决。假设 f(n) 表示到达第 n 个台阶的不同走法数目：

- 如果只爬一个台阶，就只有 1 种走法，即直接一步走，所以 f(1) = 1；
- 如果能一步走一个台阶，也能一步走两个台阶到达 n-1 或者 n-2 个台阶，因此 f(n) = f(n-1) + f(n-2)，这对应于“一步一个”和“一步两个”的组合。

递归公式就是这样的：
f(n) = f(n-1) + f(n-2), 对于 n >= 2，初始条件为 f(0) = 0 和 f(1) = 1。

递归函数实现如下（Python语言）：

def climb_stairs(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return climb_stairs(n - 2)

# 测试
n = int(input("请输入台阶数："))
ways = climb_stairs(n)
print(f"有 {ways} 种不同的走法.")

小明爬楼梯，如果每次可以上一个台阶或者两个台阶或者3个台阶，那么上 n 级台阶一共有多少种方案？

这道题可以使用递归或者动态规划来解决。

首先考虑递归，对于上 n 级台阶，小明可以从 n-1 级、n-2 级或者 n-3 级上来，所以总方案数为到 n-1 级、n-2 级和 n-3 级的方案数之和。可以得到递推公式：

f(n) = f(n-1) + f(n-2) + f(n-3)

其中 f(1) = 1, f(2) = 2, f(3) = 4。

使用递归需要注意的是，当 n 很大时，会出现重复计算的问题，导致时间复杂度变高，所以需要使用记忆化搜索或者动态规划来优化。

下面给出使用动态规划的解法：

设 dp[i] 表示到达第 i 级台阶的方案数，则有：

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

边界条件为 dp[1] = 1, dp[2] = 2, dp[3] = 4。

最终答案为 dp[n]。

代码如下（使用 Python 实现）：

def climb_stairs(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]

当输入 n=4 时，输出为 7；当输入 n=5 时，输出为 13。