JZ71跳台阶扩展问题描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。数据范围：1\len\le201≤n≤20进阶：空间复杂度O(1)O(1)，时间复杂度O(1)O(1)方法1动态规划思路：对于最后一级台阶，我们可以由倒数第二级台阶跳1步，也可以由倒数第三级太极跳两步，即f(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n)=f(0)+f(1)+f(2)+...+f(n−1)f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n)=f(0)+f(1)+f(2)+.
JZ71跳台阶扩展问题描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。数据范围：1\len\le201≤n≤20进阶：空间复杂度O(1)O(1)，时间复杂度O(1)O(1)方法1动态规划思路：对于最后一级台阶，我们可以由倒数第二级台阶跳1步，也可以由倒数第三级太极跳两步，即f(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n)=f(0)+f(1)+f(2)+...+f(n−1)f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n)=f(0)+f(1)+f(2)+.
Leetcode70题有人问我：烤冷面你这两周怎么总搞简单题？我想说：一步一步来～题干简述给定：假设你正在爬楼梯，需要爬n阶你才能到达楼顶。每次你可以爬1或2个台阶。要求：计算出有多少种爬楼梯的方式。解题思路如果我们缩小视野（把大问题化为小问题），爬到第n阶台阶有两种方式：从n-1阶爬一级台阶从n-2阶爬两级台阶用公式表达：dp[n]=dp[n−1]+dp[n−2]，其中的特例是：dp[0]=1和dp[1]=1。嚯！这不就是LeetCode509(斐波那契数列)么。代码实现classSolution:defclimbStairs(self,n:int)->int:ifn复杂度时间复杂度O(n)
Leetcode70题有人问我：烤冷面你这两周怎么总搞简单题？我想说：一步一步来～题干简述给定：假设你正在爬楼梯，需要爬n阶你才能到达楼顶。每次你可以爬1或2个台阶。要求：计算出有多少种爬楼梯的方式。解题思路如果我们缩小视野（把大问题化为小问题），爬到第n阶台阶有两种方式：从n-1阶爬一级台阶从n-2阶爬两级台阶用公式表达：dp[n]=dp[n−1]+dp[n−2]，其中的特例是：dp[0]=1和dp[1]=1。嚯！这不就是LeetCode509(斐波那契数列)么。代码实现classSolution:defclimbStairs(self,n:int)->int:ifn复杂度时间复杂度O(n)
问题一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n 级的台阶总共有多少种跳法。答案需要取模1e9+7（1000000007），如计算初始结果为：1000000008，请返回1。解决1、动态规划classSolution{publicintnumWays(intn){//**3.动态规划**：穷举可以发现f(n)=f(n-1)+f(n-2);确定边界：f(0)=1,f(1)=1,f(2)=2;最佳解f(n)=f(n-1)+f(n-2);得到最终解决方案(边界+最优解)if(n==0)return1;if(nmap=newHashMap();//定义hashmap应该放在方法
问题一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n 级的台阶总共有多少种跳法。答案需要取模1e9+7（1000000007），如计算初始结果为：1000000008，请返回1。解决1、动态规划classSolution{publicintnumWays(intn){//**3.动态规划**：穷举可以发现f(n)=f(n-1)+f(n-2);确定边界：f(0)=1,f(1)=1,f(2)=2;最佳解f(n)=f(n-1)+f(n-2);得到最终解决方案(边界+最优解)if(n==0)return1;if(nmap=newHashMap();//定义hashmap应该放在方法
循环迭代： 1publicclasssteps{2publicintjs(intn){3intone=2;//初始化为第三级台阶最后跨一步的走法4inttwo=1;//初始化为第三级台阶最后跨两步（一下迈过去两个台阶）的走法5intsum=0;//总走法6for(inti=3;i){7sum=one+two;//当i=3时，sum为最后跨一步one：到2级台阶的走法+最后跨两步two：到1级台阶的走法8two=one;//3级台阶最后跨一步的走法赋值给two，第4级台阶最后跨两步走法就是3级台阶最后跨一步的走法，即到2级台阶的走法9one=sum;//将3级台阶的总走法赋值给one，第4级台
循环迭代： 1publicclasssteps{2publicintjs(intn){3intone=2;//初始化为第三级台阶最后跨一步的走法4inttwo=1;//初始化为第三级台阶最后跨两步（一下迈过去两个台阶）的走法5intsum=0;//总走法6for(inti=3;i){7sum=one+two;//当i=3时，sum为最后跨一步one：到2级台阶的走法+最后跨两步two：到1级台阶的走法8two=one;//3级台阶最后跨一步的走法赋值给two，第4级台阶最后跨两步走法就是3级台阶最后跨一步的走法，即到2级台阶的走法9one=sum;//将3级台阶的总走法赋值给one，第4级台
