笔试题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。该题有三种解法：递归的方法求解斐波那契数列、用概率与统计的数学方法解决，３.动态规划

末蓝、 2022-12-24 12:53 128阅读 0赞

### 笔试题 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。该题有三种解法：1.递归的方法求解斐波那契数列、2.用概率与统计的数学方法解决，３.动态规划 ###

*  该题有三种解法：
 *   *  一、递归的方法求解斐波那契数列
     *  二、用概率与统计的数学方法解决
     *  三、动态规划

)

# 该题有三种解法： #

## 一、递归的方法求解斐波那契数列 ##

有ｊ个台阶的时候，可以一次跳１步，再跳完ｊ－１个台阶，也可以一次跳两步，再跳ｊ－２个台阶，故ｆ（ｊ）＝ｆ（ｊ－１）＋ｆ（ｊ－２），聪明的学习者可以发现，这一步和斐波那契数列特别像，没错！这就是一个斐波那契数列，用递归的方法来解决就可以了。  
求解斐波那契数列的两种方法在这篇博客中：https://blog.csdn.net/qq\_36079986/article/details/110246881

def fbnq(n):
        if n ==0:
            return 0
        elif n ==1:
            return 1
        else:
            return fbnq(n-2) + fbnq(n-1)
    print(fbnq(n))

## 二、用概率与统计的数学方法解决 ##

之前面试的时候第一次见到这道题，洋洋洒洒写了一大页，用概率与统计的方法解决了，具体方法在另外一篇博客中。

## 三、动态规划 ##

public static int MaxChildArrayOrder(int a[]) { 
    		int n = a.length;
    		int temp[] = new int[n];//temp[i]代表0...i上最长递增子序列
    		for(int i=0;i<n;i++){ 
    			temp[i] = 1;//初始值都为1
    		}
    		for(int i=1;i<n;i++){ 
    			for(int j=0;j<i;j++){ 
    				if(a[i]>a[j]&&temp[j]+1>temp[i]){ 
    					//如果有a[i]比它前面所有的数都大，则temp[i]为它前面的比它小的数的那一个temp+1取得的最大值
    					temp[i] = temp[j]+1;
    				}
    			}
    		}
    		int max = temp[0];
    		//从temp数组里取出最大的值
    		for(int i=1;i<n;i++){ 
    			if(temp[i]>max){ 
    				max = temp[i];
    			}
    		}
    		return max;
    	}