跳台阶与变态跳台阶解法（Java实现）

谁践踏了优雅 2022-05-18 03:13 171阅读 0赞

这两道题博主都是用的数学归纳法。

首先

# **一.跳台阶** #

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

情况：

1阶：跳1次

2阶：跳2次

3阶：跳3次

4阶：跳5次

5阶：跳8次

6阶：跳13次

7阶：跳21次

1,2,3,5,8,13,21····

**从次数可以看出是一种数列，那就是斐波那契数列，规律是第n+1项等于n项  +（n-1）项：![a+a\_\{n-1\}=a\_\{n+1\}][a_a_n-1_a_n_1]**

关于斐波那契数列的解释：

[https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin][https_baike.baidu.com_item_E6_96_90_E6_B3_A2_E9_82_A3_E5_A5_91_E6_95_B0_E5_88_97_99145_fr_aladdin]

**因此此题变成求从1开始，斐波那契数列的第n项是什么？**

public class Solution {
    	public int JumpFloor(int target) {
    		if (target == 0) {
    			return 0;
    		}
    		int[] a = new int[target + 2];//加2是因为必须加到target本身，因此+1,又因为从i-1=0（i=1）开始循环，需要数组a[0]再装下一个0,因此再+1。
    		a[0] = 0;
    		a[1] = 1;
    		for (int i = 1; i < target + 1; i++) {
    
    			a[i + 1] = a[i] + a[i - 1];
    
    		}
    		return a[target + 1];
    	}
    }

# 二.变态跳台阶 #

这个题如果程序不长，不过需要理解它的原理：

情况：

**数学归纳法**

1阶：1种

2阶：2种

3阶：4种

4阶：8种

5阶：16种

再往下就是一直第n阶级，到![2^\{n-1\}][2_n-1]

**或者用推理的方式：**

**首先直接看3阶的：3阶有4种情况。3阶对应4种情况=》3J=4Q**

![70][]

**那跳4阶的时候：a情况：第0阶到第3阶****(3阶的情况)****有4种，最后跳1个****阶跳到第4阶，**

**                           b情况：第0阶跳1个阶先跳到第1阶，第1阶到第4阶****(3阶的情况)****有4种。**

![70 1][]

** a与b中，因为第3阶到第4阶只增加1阶。**

**所以a****情况中，前3阶中的4种情况中的一种是 每次只跳1阶，最后跳1阶登顶与b情况中先跳1个阶跳到第1阶，后3阶中的4种情况中的一种 每次只跳1阶，其实同为一种。因为当出现这a，b两种情况 中 各四种情况中的每次只跳1阶，都是相当于，全程每次只跳1阶。重复计算了一种每次只跳1阶的情况。**

**4阶：**

**4+4=8**

**8-1=7种**

**但是再算上从0阶直接跳到4阶的一种，又为8种。**

4阶到5阶也是一样：4阶为8种

5阶中的前4阶加最后1阶为a1情况，5阶第1阶加后4阶为b1情况

**5阶：**

**8+8=16**

**16-1=15//减一为a1与b1中重复计算了一次每次只跳1阶的情况**

**15+1=16//加一为全阶一次跳完的情况**

这样往后推就能知道

每次增加1个台阶，之前的情况都会翻倍

这样就能得到等比数列的通项公式 ![a\_\{n\}][a_n]=![a\_\{1\}][a_1]![q^\{n-1\}][q_n-1] ：![a\_\{1\}][a_1]=1，q=2

通项公式出来了。程序也就很简单了

public class Solution {
        public int JumpFloorII(int target) {
            return 1<<target-1;//根据等比通项公式 a1*q^(n-1)
        }
    }

画图辛苦，点个赞吧！

[a_a_n-1_a_n_1]: https://private.codecogs.com/gif.latex?a&plus;a_%7Bn-1%7D%3Da_%7Bn&plus;1%7D
[https_baike.baidu.com_item_E6_96_90_E6_B3_A2_E9_82_A3_E5_A5_91_E6_95_B0_E5_88_97_99145_fr_aladdin]: https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin
[2_n-1]: https://private.codecogs.com/gif.latex?2%5E%7Bn-1%7D
[70]: /images/20220518/f5d957501a074f54969c924ad63e9af3.png
[70 1]: /images/20220518/3923cef69b3f40fca94b571054a80c31.png
[a_n]: https://private.codecogs.com/gif.latex?a_%7Bn%7D
[a_1]: https://private.codecogs.com/gif.latex?a_%7B1%7D
[q_n-1]: https://private.codecogs.com/gif.latex?q%5E%7Bn-1%7D