变态跳台阶

1. 题目描述

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

2. 思路

• 公式法

// 式子1：f(n) = f(n-1) + f(n-2) + ... + f(1)
// 式子2：f(n-1) = f(n-2) + ... + f(1)
// 式子1-式子2 -> f(n) = 2f(n-1)

• 找规律

//1 1
//2 2
//3 4
//4 8
//n 2^(n-1)

3. 实现

3.1. 公式法

// 式子1：f(n) = f(n-1) + f(n-2) + ... + f(1)
// 式子2：f(n-1) = f(n-2) + ... + f(1)
// 式子1-式子2 -> f(n) = 2f(n-1)
//时间复杂度：O(n)
//空间复杂度：O（1）
func JumpFloorII(number int) int {
	if number == 1 {
		return number
	}

	a := 1
	res := 2 * a
	for i := 2; i < number; i++ {
		a = res
		res = 2 * a
	}
	return res
}

3.2. 找规律

//找规律
//1 1
//2 2
//3 4
//4 8
//n 2^(n-1)
//时间复杂度：O(1)
//空间复杂度：O（1）
func JumpFloorII2(number int) int {
	if number <= 1 {
		return 1
	}
	return 2 << (number - 2)
}

4. 参考

• 变态跳台阶_牛客网