动态规划解决小青蛙跳台阶问题题目描述一、思路分析二、代码实现

题目描述

入门版：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

变态版：一只青蛙一次可以跳上1级台阶，也可以跳上2级，也可以跳n级，求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

一、思路分析

入门版：

进阶版：

二、代码实现

/**
 * 青蛙跳台阶问题
 *
 * @author JiaMing
 * @since 2021/12/29/0029 下午 14:05
 **/

public class FrogJump {
    public static void main(String[] args) {
        System.out.println("普通版4级台阶跳法"+jump(4));
        System.out.println("变态版4级台阶跳法"+jumpN(4));
    }

    //普通版：青蛙一次可以跳一级台阶，或者跳二级，求它跳上N级台阶有几种方法
    //递归：可能性函数关系 f(n) = f(n - 1) + f(n -2)

    public static int jump(int stepNumber) {
        //如果只有一级台阶，那么只有一种方式
        if (stepNumber == 1) {
            return 1;
        } else if (stepNumber == 2) { //如果有两级台阶，那么有两种方式
            return 2;
        } else {

            return jump(stepNumber - 1) + jump(stepNumber - 2);
        }
    }

    //进阶版：青蛙一次可以跳一级台阶，也可以跳二级，它也可以跳上n级
    //动态规划：转移方程 f(n)=2*f(n - 1)
    public static int jumpN(int stepNumber) {
        if (stepNumber <= 1) {
            return stepNumber;
        }
        //左移一位表示 * 2
        return 1 << (stepNumber - 1);
    }

}

最后

以上就是朴素豌豆为你收集整理的动态规划解决小青蛙跳台阶问题题目描述一、思路分析二、代码实现的全部内容，希望文章能够帮你解决动态规划解决小青蛙跳台阶问题题目描述一、思路分析二、代码实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。