回溯法-变态跳台阶

牛客网-变态跳台阶

内容描述

题目描述

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

解题思路

尝试使用回溯法进行解决问题,遍历全部方法,从而找到跳法(本题目有更简单的方法,见后面)

回溯法模板

try(int i)
{
     if(i>n)
         输出结果;
     else
     {
         for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径
        {
                   if(fun(j)) // 满足限界函数和约束条件
                  {
                 a[i] = j;
                 ... // 其他操作
                 try(i+1);
                 回溯前的清理工作（如a[i]置空值等）;
             }
         }
     }
           

实现代码(java)

public class Solution {
    public  int JumpFloorII(int target) {
        int count=0;
        int sum=0;
        count=digui(target,sum,count);
        return count;
    }
    public  int digui(int target,int sum,int count) {
        if (target==sum){
            count++;
            return count;
        }
        else {
            for(int i=target-sum;i>0;i--){
                if (sum+i<=target){
                    sum=sum+i;
                    count=digui(target,sum,count);
                    sum=sum-i;
                }

            }
        }
        return count;
    }


}
           

简单方法

查看牛客网通过的代码发现简单方法,由于都能跳,所以每个台阶的状态只有被跳了和没被跳,因此总方法数是2的n-1次方