LeetCode面试题10-II.青蛙跳步[简志Offer][Easy][Python][动态编程]问题青蛙一次可以跳一级或两级。求青蛙跳上n级台阶的跳跃方法总数。答案需要取模1e9+7(1000000007)。如果初始计算结果为：1000000008，请返回1。例1：输入：n=2输出：2例2：输入：n=7输出：21提示：0<=n<=100注：本题为与主站点上的问题70相同。思路动态规划的初始条件和斐波那契数列有点不同：dp_0=1,dp_1=1.fib(n)=fib(n-1)+fib(n-2)注意fib(n)将是越界，所以最好：fib(n)%1000000007=(fib(n-1)%1000000007+fib(n-2)%1000000007)%1000000007但是因为Python中整数的大小限制取决于计算机的内存（可以理解为无限大），大数越界的问题可以忽略。时间复杂度：O(n)空间复杂度：O(1)Python3代码类解：defnumWays(self,n:int)->int:#初始条件不同于斐波那契数列dp_0,dp_1=1,1for_在范围内（n）：dp_0，dp_1=dp_1，dp_0+dp_1返回dp_0%1000000007GitHublinkPython
