题解 | #跳台阶扩展问题#

动态规划,由于 n 个台阶可以 1, ... n 都可以调过来,状态转移通过 0, 1, ... n - 1 转移 dp[i] = dp[j] j < i

import sys
n = int(sys.stdin.readline().strip())
if n == 1:
    print(1)
    exit()
if n == 2:
    print(2)
    exit()
dp = [0 for _ in range(n + 1)]
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
    for j in range(i):
        dp[i] += dp[j]
print(dp[-1])