27528: 跳台阶

dp, http://cs101.openjudge.cn/practice/27528/

理科教学楼总共有N级台阶，狄贵同学每一步可以走的台阶数目可以是1、2、3、... 、N-1、N中的任意一个。 请问狄贵可以有多少种不同的走法走上这N级台阶。

输入

总共一行输入，输入台阶的阶数N。 其中，1 <= N <= 25。

输出

多少种不同的走法走上N级台阶。

样例输入

3

样例输出

4

设$d{p}_i$为上$i$级台阶的方案数，则有$d{p}_0=1,d{p}_i=\sum _{j=0}^{i-1}d{p}_j(i\ge 1)$，据此计算即可。

# 周晟昱 24工学院
dp = [0] * (int(input()) + 1)
dp[0] = 1
for i in range(1, len(dp)):
    dp[i] = sum(dp[:i])
print(dp[-1])

def count_ways(N):
    if N == 1:
        return 1
    dp = [0] * (N + 1)
    dp[0] = 1  # Base case: 1 way to stay at the ground (0 steps)
    
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            dp[i] += dp[i - j]
    
    return dp[N]

if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    N = int(input().strip())
    print(count_ways(N))