剑指offer面试题牛客_递归和循环_跳台阶(java版)

welcome to my blog

剑指offer面试题牛客_递归和循环_跳台阶(java版):

题目描述

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

思路

• 设f(n)表示跳上n阶台阶的跳法数量, 因为青蛙一次能跳一阶或者两阶, 所以f(n)和f(n-1),f(n-2)满足递归关系式: f(n) = f(n-1) + f(n-2)
• 可以使用递归函数求解, 递归函数的逻辑: 计算跳上n阶台阶的跳法数量
• 递归终止条件, 跳上1阶时,返回1; 跳上2阶时返回2
• 使用递归函数求解是自顶向下的求解方式, 会产生很多重复计算, 可以使用循环替代递归函数, 循环是自底向上的, 可以利用已有的结果, 从而避免重复计算

递归版

public class Solution {
    public int JumpFloor(int target) {
        /*
        思路: 设f(n)是跳上n级台阶的跳法, 青蛙一次能跳一阶或者两阶, 所以有f(n) = f(n-1) + f(n-2)
        很明显,可以用递归. 递归终止条件f(1)=1, f(2)=2, f(3)=f(2)+f(1)=3
        递归函数的逻辑: 计算跳上n阶台阶的跳法数量
        */
        if(target == 1) return 1;
        if(target == 2) return 2;
        return JumpFloor(target-1) + JumpFloor(target-2);
    }
}

循环版(推荐, 因为避免了很多重复计算)

public class Solution {
    public int JumpFloor(int target) {
        //input check
        if(target <=0) return 0;
        //execute
        if(target == 1) return 1;
        if(target == 2) return 2;
        // 使用数组表示跳上i阶台阶的跳法数量
        int[] arr = new int[target+1]; 
        arr[1] = 1;
        arr[2] = 2;
        for(int i=3; i<= target; i++){
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr[target];
    }
}