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)
  • 不管是递归还是带备忘录的递归都是至上而下的,而动态规划是至下而上;
  • 递归有大量的重复操作,而带备忘录的递归和动态规划每次操作都只执行一次,从而大大节省了时间

原创文章,作者:jamestackk,如若转载,请注明出处:https://blog.ytso.com/273573.html

(0)
上一篇 2022年7月11日
下一篇 2022年7月11日

相关推荐

发表回复

登录后才能评论