java算法:青蛙跳台阶问题(经典算法)
2022/7/11 1:22:41
本文主要是介绍java算法:青蛙跳台阶问题(经典算法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题
- 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
解决
class Solution { static int MOD=1000000007; public int numWays(int n) { // **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) return 1; if(n<=2) return n; int a=1,b=1,c=2; for(int i=3;i<=n;i++){ //可以近似看作一个不断移动的数组,后面一个值等于前两个相加 b=a; a=c; c=(a+b)%MOD; } return c; } } // 青蛙跳台阶: // 递归、带备忘录的递归、动态规划 // **1.递归** // public int numWays(int n) { // if(n==1) return 1; // if(n==2) return 2; // return numWays(n-1)+numWays(n-2); // } //**2. 带备忘的递归(减少了递归过程中的重复操作)** // static int MOD=1000000007; // HashMap<Integer,Integer> map=new HashMap(); //定义hashmap应该放在方法外面,在不方法每次调用都会创一个新的hashmap // public int numWays(int n) { // if(n==0) return 1; // if(n<=2) return n; // if(map.containsKey(n)) //检查 hashMap 中是否存在指定的 key 对应的映射关系。 // { // return map.get(n); //如果备忘里存在就直接返回。 // }else{ // map.put(n,(numWays(n-1)+numWays(n-2))%MOD); // return map.get(n); // } // // return numWays(n-1)+numWays(n-2); // }
总结
- 时间复杂度分析:(1.递归)-O(n^2)---(2.带备忘的递归)-O(n)---(3.动态规划)-O(n)
- 不管是递归还是带备忘录的递归都是至上而下的,而动态规划是至下而上;
- 递归有大量的重复操作,而带备忘录的递归和动态规划每次操作都只执行一次,从而大大节省了时间
这篇关于java算法:青蛙跳台阶问题(经典算法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南