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, 2
for i in range(3, n + 1):
for j in range(i):
dp[i] += dp[j]
print(dp[n])
原文地址：https://blog.csdn.net/qq_41094332/article/details/140614591
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！