动态规划–爬楼梯
爬楼梯
题目： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。
示例 1： 输入： 2 输出： 2
示例 2： 输入： 3 输出： 3
【分析】
题目中说只能爬一个台阶或两个台阶
那么：爬到第N阶方法数=再 爬一个台阶的方法+再 爬两个台阶的方法
第1阶：1+0 1
第2阶：1+1 2
第3阶：2+1 3（ps：再爬一个台阶;即从第2开始爬，爬到2的方法有两种，那么这两种从2到3都是爬1阶，所以再爬一个台阶方法有两种，爬两个台阶：从1开始，到一方法只有一种，1到3阶就是再一次爬两阶）
依次类推
可以得到一个递推式;F(n)=F(n-1)+F(n-2) (F表示方法数，n表示台阶数)
即可转化为斐波拉切数列问题
代码
n=int(input()) dp=[0]*n+1 dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2] print(dp[n])
