题解 | #跳台阶扩展问题#

题目

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

思路

本题也是采用递归的思想。青蛙跳1级或者2级时，跳的方法总数分别是1和2，也就是F(n)=n,(n=1,2)；当青蛙跳＞2级时，由于青蛙可以跳1级，2级，也可以跳n-1级，n级，所以青蛙的第一跳其实有n种跳法，假设青蛙跳了m跳，那么其实只要看剩下的n-m跳有几种跳法就可以了，那么n-m跳的第一跳也是有n-m种跳法，实际n-m有多少种跳法也是看每跳后剩下有几种跳法。不过有一个注意的点：当青蛙总共需要上n级台阶时，第一跳跳了n级，剩下0跳，本来0跳sum+=0的，但是跳了n级也是一种跳法，所以sum++。

代码

public class Solution {
    public int jumpFloorII(int target) {
        //跳的种数，初始化为0
        int sum = 0;
        if(target == 0 || target == 1 || target == 2){
            sum+=target;
        }else if(target > 2){
            for(int i=1;i<=target;i++){
                if(i<target){
                    sum+=jumpFloorII(target-i);
                }else{
                    //当青蛙一共需要跳n级台阶，第一跳跳n级，方法总数sum+1
                    sum++;
                }
            }
        }
        return sum;
    }
}