剑指offer之面试题9-3：变态跳台阶

本文主要是介绍剑指offer之面试题9-3：变态跳台阶，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路：用数学归纳的思想，分析得出规律。
台阶数为1，先跳一阶，剩下的跳法为f(1-1)=f(0)。
台阶数为2，先跳一阶，剩下的跳法为f(2-1)=f(1)；先跳2阶，剩下的跳法为f(2-2)=f(0)，由加法原理，f(2)=f(1)+f(0)
……
台阶数为n，先跳一阶，剩下的跳法为f(n-1)，…，先跳n-1阶剩下的跳法为f(1)，先跳n阶，剩下的跳法为f(0)，由加法原理，f(n)=f(n-1)+…+f(1)+f(0)=2*f(n-1)

经过以上分析，可得到如下代码，牛客网成功提交：

import java.util.Arrays;
public class Solution {public static int JumpFloorII(int target) {int[] result={1,1,2};result=Arrays.copyOf(result, target+1);if(target<=2)return result[target];for(int i=3;i<=target;i++){int temp=0;for(int j=0;j<i;j++){temp=temp+result[j];}//System.out.println(temp);result[i]=temp;}return result[target];}public static void main(String[] args){int target=10;System.out.println(JumpFloorII(target));}
}

递归方法

import java.util.Arrays;
public class Solution {public static int JumpFloorII(int target) {if(target <= 0) return -1;if(target == 1) return 1;return 2 * JumpFloorII(target - 1);}
}

这篇关于剑指offer之面试题9-3：变态跳台阶的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---