204、【动态规划】牛客网 ——DP3 跳台阶扩展问题（Python版本）
题目描述
原题链接：DP3 跳台阶扩展问题
解题思路
一个DP问题，相比于普通爬楼（只能爬一层或者两层）对应的状态函数为 d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] dp[i] = dp[i - 1] + dp[i - 2] dp[i]=dp[i−1]+dp[i−2]。本题的dp是各层方式都可以，那么就是 d p [ i ] = ∑ j = 1 n d p [ i − j ] dp[i] = \sum_{j=1}^ndp[i-j] dp[i]=∑j=1ndp[i−j]，其中 j = n j=n j=n时，为1，表示从第一层台阶直接跳到第n层。
初始化dp：dp[0] = 1, dp[1] = 1, dp[2] = 2
代码
n = int(input())
if n <= 2:print(n)
else:dp = [0] * (n + 1)# dp数组初始化dp[0], dp[1], dp[2] = 1, 1, 2for i in range(3, n + 1): for j in range(i):dp[i] += dp[j]print(dp[n])