百度&必应权4, 日IP8000. 查看详情
自助收录

使用循环(迭代)法替代递归法优化“青蛙跳台阶”问题

算法刷题2年前 (2023)更新 江南白衣
321 0 0
使用循环(迭代)法替代递归法优化“青蛙跳台阶”问题

题目:青蛙跳台阶
描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路:前面我们用递归的思想很快解决了青蛙跳台阶的问题。但是递归这种方法有一个很大的缺陷,就是过程中存在大量的重复计算。如果题目要求的数字过大,程序运算出结果会花费非常多的时间,所以我们要知道比递归更好的方法才能打动面试官,受到公司的青睐。

使用循环(迭代)法替代递归法优化“青蛙跳台阶”问题

优化方式一:循环(迭代)法
优化方式二:带缓存结构的递归法,参考:https://www.codernav.com/2809.html
优化方案三:动态规划法,参考:https://www.codernav.com/2802.html
画图分析:

使用循环(迭代)法替代递归法优化“青蛙跳台阶”问题

给大家解释一下上图:
开始f3 = 3,f2 = 2,f1 = 1,
我们先让f3 = f1 + f2,这么没问题吧,1+2=3
再来我们把f2的值赋给f1,此时f1就等于2,
再把f3的值赋给f2,此时f2的值就等于3
循环起来,那此时再求f3的值就是2+3=5,恰好就是我们4阶台阶的5种跳法。
代码实现:

package od;

/**
 * 青蛙跳台阶
 * 问题描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * 原文地址:https://www.codernav.com/2806.html
 */
public class OdTest13 {
    public static int frogJump2(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        int f1 = 1;
        int f2 = 2;
        int f3 = 0;
        for (int i = 3; i <= n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }

    public static void main(String[] args) {
        System.out.println(frogJump2(10));
    }
}

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...