n = int(input()) lst = [0] * (n+1) if n == 1 or n == 2: print(n) exit() lst[0] = 1 lst[1] = 1 lst[2] = 2 for i in range(3, n+1): for j in range(i): lst[i] += lst[j] print(lst[-1])
两个for,外面的for和跳台阶的一样,内层的for就是用来实现从1~n-1的方法数累加的 -》 等价于方法数的n-1 + n-2 + n-3 + ..... + 0
设置了lst[0] = 1其实就是一下子从1到n层的一种,不要也行,dp[-1]+1即可