P1255 数楼梯

题目

题目描述

楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 60% 的数据，N≤50；
对于 100% 的数据，1≤N≤5000。

问题分析

我们可以用递归角度解决：

当青蛙跳到第 n 级楼梯，可以选择：
- 从第 n-1 级跳到第 n 级（跳 1 级）。
- 从第 n-2 级跳到第 n 级（跳 2 级）。
递归关系：
- f(n)=f(n−1)+f(n−2)
  - 其中，f(n) 代表跳到第 n 级楼梯的方法总数。
  - 并且：
    - 如果 n=0，即青蛙在第 0 级楼梯，则 f(0)=0（即什么都不做）。
    - 如果 n=1，即青蛙跳到第 1 级楼梯，那么只能跳 1 级，则 f(1)=1。
问题的递归式：
- 基于以上推理，我们可以列出以下递归关系式：

解题

伪代码：

F(n):
    如果 n == 0:
        返回1     // 起始点，不需要跳跃，只有一种方式
    如果 n == 1:
        返回 1    // 只有一种方式跳到第1阶

    // 从n-1阶跳到n阶，或从n-2阶到n阶
    返回 CountWays(n - 1) + CountWays(n - 2)

Python 实现：
初版：

def F(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return F(n - 1) + F(n - 2)
    
n = input()
print(F(n))

犯了个低级错误，输入的 n 是字符串。

改正：

def F(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return F(n - 1) + F(n - 2)
    
n = int(input())
print(F(n))

OK，提交代码：

WA、TLE、RE。。。。。。

应该是效率太低了，难道要用DP解？

DP（动态规划）

定义：
- 设 dp[i] 表示青蛙跳到第 n 级台阶的方法数。
- 当 i>=2 时，青蛙可以选择：
  - 从第 i-1 级楼梯跳到第 n 级。
  - 从第 i-2 级楼梯跳到第 n 级。
- 所以，我们可以列出：
  - dp[i]=dp[i−1]+dp[i−2]
    - 并且：
      - 如果 i=0，dp[0]=1，表示跳到第0阶的方式只有1种（就是不跳）。
      - 如果 i=1，dp[1]=1，表示跳到第1阶的方式只有1种（就是跳 1 级）。
递推关系：
- 那么，我们很容易得出递推公式：
  - dp[i]=dp[i−1]+dp[i−2]
- 通过递推公式，从 dp[2] 一直到 dp[n]，逐步计算出结果。

解题（DP）

Python实现：

def F(n):
    # 如果 n 为 0 或 1，直接返回 1
    if n == 0 or n == 1:
        return 1
    
    # 创建一个 dp 数组，存储每阶的跳法
    dp = [0] * (n + 1)
    
    # 初始条件
    dp[0] = 1  # 第 0 阶只有 1 种方法（不跳）
    dp[1] = 1  # 第 1 阶只有 1 种方法（跳 1 步）
    
    # 递推关系，计算从第 2 阶到第 n 阶的方法数
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    # 返回跳到第 n 阶的方法数
    return dp[n]

# 读取输入
n = int(input())
print(F(n))

提交！
AC！
完美通过！
本篇题解到此结束，