假设有2种上楼梯的步伐:1个台阶/步,2个台阶/步。从1楼到2楼有n级台阶。有多少种不同的走法。 输入一行,一个整数n,n<30,表示台阶数。 编写程序,输出一行,一个整数,表示不同走法的个数。

这是一道经典的动态规划问题，可以使用递归或迭代的方式进行解决。以下是一个使用迭代的 Python 代码实现：

n = int(input())

# 初始化数组
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]

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

这段代码中，我们使用 `dp` 数组记录了每个台阶数对应的不同走法数量，初始值为 1，因为只有一种走法（一步一步走）或者 2 种走法（跨两步）。然后，我们通过迭代的方式计算出每个台阶数对应的不同走法数量，直到计算到 `n` 台阶数为止。最后输出 `dp[n]` 即可得到结果。

相关问题

假设有2种上楼梯的步伐：1个台阶/步，2个台阶/步。从1楼到2楼有n级台阶。有多少种不同的走法。

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

首先考虑递归方法。设 `f(n)` 表示走到第 `n` 级台阶的不同走法数量，则有以下递推式：

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

解释一下，走到第 `n` 级台阶可以从第 `n-1` 级台阶走一步或者从第 `n-2` 级台阶走两步到达。当 `n=1` 时，只有一种走法；当 `n=2` 时，有两种走法（一步一步走或者直接跨两步）。

根据递推式，可以编写如下的递归函数来求解：

def count_ways(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return count_ways(n-1) + count_ways(n-2)

然而，这种递归方法会有很多重复计算，导致时间复杂度非常高，随着 `n` 的增加，计算时间会指数级增长。

因此，我们可以使用动态规划（DP）来优化算法。具体来说，我们可以使用一个数组 `dp` 来记录到每个台阶的不同走法数量，初始值为 `dp[1] = 1, dp[2] = 2`，然后使用递推式 `dp[i] = dp[i-1] + dp[i-2]` 来计算剩余的值。最后，返回 `dp[n]` 即可。

下面是使用动态规划的代码实现：

def count_ways(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        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` 级台阶的不同走法数量了。

Python,假设有2种上楼梯的步伐：1个台阶/步，2个台阶/步。从1楼到2楼有n级台阶。有多少种不同的走法。

这是一个经典的斐波那契数列问题。假设到达第n个台阶有f(n)种走法，那么显然当第一步走了1个台阶时，剩下的n-1个台阶的走法就是f(n-1)；当第一步走了2个台阶时，剩下的n-2个台阶的走法就是f(n-2)。因此，到达第n个台阶的总走法数就是f(n) = f(n-1) + f(n-2)。同时，f(1) = 1，f(2) = 2。根据这个递推式，我们可以用递归或动态规划的方式求解。

以下是使用递归方式实现的Python代码：

def climbStairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return climbStairs(n-1) + climbStairs(n-2)

以下是使用动态规划方式实现的Python代码：

def climbStairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        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]

以上两种方式的时间复杂度都是O(n)，空间复杂度也都是O(n)。如果要优化空间复杂度，可以只用两个变量来保存前两个状态，而不用一个数组保存所有状态。