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

#先列出规则
#台阶数     跳跃顺序
#1        1
#2        11 2
#3        111 21 12 3 第三个台阶可以有3种跳法，1、可以看做是以第二个台阶跳一步可以到达第三个台阶，那么跳跃顺序为111 21（跟到达第二台阶方法数一样）。   2、看做从第一个台阶跳两步达到第三个台阶，也就是12。所以第三个台阶总的跳跃方法就是2者相加  3、直接跳3个台阶，也就是3
#4        1111 211 121 31 112 22 13 4   #第四个台阶那就有4种跳法，1、第3个台阶跳一步到达4个台阶，那么跳跃顺序为1111 211 121 31。  2、第2个台阶跳两步达到第4个台阶，跳跃顺序为112 22。 3、第1个台阶跳3步，跳跃顺序为13  4、一步到位，跳跃顺序：4
#规律已经出来了。 n个台阶跳法为前n-1个台阶跳法总和，再加上一步到位的顺序
# dp公式：dp[n] = sum(dp[:n])+1
n = int(input())
dp = [1 for i in range(n)]
for i in range(1, n):
    dp[i] = sum(dp[:i])+1
print(dp[n-1])